@inproceedings{avw-isdcm-23,
author = {Oswin Aichholzer and Birgit Vogtenhuber and Alexandra Weinberger},
title = {{{Isomorphisms of simple drawings of complete multipartite graphs}}},
booktitle = {Abstracts of the XX Spanish Meeting on Computational Geometry},
pages = {59},
year = 2023,
address = {Santiago de Compostela, Spain},
url = {https://egc23.web.uah.es/wp-content/uploads/2023/07/EGC2023_Booklet.pdf#page=71},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{agtvw-rrsgt-23,
author = {Oswin Aichholzer and Alfredo Garc{\'i}a and Javier Tejel and Birgit Vogtenhuber and Alexandra Weinberger},
title = {{{Recognizing rotation systems of generalized twisted drawings in $O(n^2)$ time}}},
booktitle = {Abstracts of the XX Spanish Meeting on Computational Geometry},
pages = {69},
year = 2023,
address = {Santiago de Compostela, Spain},
url = {https://egc23.web.uah.es/wp-content/uploads/2023/07/EGC2023_Booklet.pdf#page=81},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{agtvw-crsgt-23,
author = {Oswin Aichholzer and Alfredo Garc{\'i}a and Javier Tejel and Birgit Vogtenhuber and Alexandra Weinberger},
title = {{{Characterizing rotation systems of generalized twisted drawings via 5-tuples}}},
booktitle = {Abstracts of the XX Spanish Meeting on Computational Geometry},
pages = {71},
year = 2023,
address = {Santiago de Compostela, Spain},
url = {https://egc23.web.uah.es/wp-content/uploads/2023/07/EGC2023_Booklet.pdf#page=83},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{mpsv-bcpcd-19,
author = {Carolina Medina and Irene Parada and Gelasio Salazar and Birgit Vogtenhuber},
title = {{{Bounding the number of crossings for a particular class of drawings of $K_{n,n}$}}},
booktitle = {Proc. XVIII Encuentros de Geometr\'{\i}a Computacional},
pages = {34},
year = 2019,
address = {Girona, Spain},
pdf = {/files/publications/geometry/mpsv-bcpcd-19.pdf},
url = {http://imae.udg.edu/egc2019/doc/BookAbstractsEGC2019.pdf},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{fkmottuv-prpcp-19a,
author = {David Flores-Pe{\~n}aloza and Mikio Kano and Leonardo Mart{\'i}nez-Sandoval and David Orden and Javier Tejel and Csaba D. T{\'o}th and Jorge Urrutia and Birgit Vogtenhuber},
title = {{{Perfect rainbow polygons for colored point sets in the plane}}},
booktitle = {Proc. XVIII Encuentros de Geometr\'{\i}a Computacional},
pages = {43--46},
year = 2019,
address = {Girona, Spain},
pdf = {/files/publications/geometry/fkmottuv-prpcp-19a.pdf},
url = {http://imae.udg.edu/egc2019/doc/BookAbstractsEGC2019.pdf},
abstract = {Given a planar $n$-colored point set $S= S_1 \cup \ldots \cup S_n$ in general position, a simple polygon $P$ is called a \emph{perfect rainbow} polygon if it contains exactly one point of each color. The \emph{rainbow index} $r_n$ is the minimum integer $m$ such that every $n$-colored point set $S$ has a perfect rainbow polygon with at most $m$ vertices. We determine the values of $r_n$ for $n \leq 7$, and prove that in general $\frac{20n-28}{19} \leq r_n \leq \frac{10n}{7} + 11$.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{fkmottuv-prpcp-19b,
author = {David Flores-Pe{\~n}aloza and Mikio Kano and Leonardo Mart{\'i}nez-Sandoval and David Orden and Javier Tejel and Csaba D. T{\'o}th and Jorge Urrutia and Birgit Vogtenhuber},
title = {{{Perfect rainbow polygons for colored point sets in the plane}}},
booktitle = {Proc. 22nd Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG3 2019)},
pages = {57--58},
year = 2019,
address = {Tokyo, Japan},
url = {http://www.jcdcgg.u-tokai.ac.jp/JCDCG3_2019_abstracts_v1.pdf},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{ahvv-nng4h-16,
author = {Oswin Aichholzer and Thomas Hackl and Pavel Valtr and Birgit Vogtenhuber},
title = {{{A Note on the Number of General 4-holes in (Perturbed) Grids}}},
booktitle = {Discrete and Computational Geometry and Graphs. JCDCGG 2015.},
series = {Lecture Notes in Computer Science (LNCS)},
volume = {9943},
editor = {Akiyama, Jin and Ito, Hiro and Sakai, Toshinori and Uno, Yushi},
publisher = {Springer, Cham},
pages = {1--12},
year = 2016,
e-isbn = {978-3-319-48532-4"},
isbn = {978-3-319-48531-7},
doi = {https://doi.org/10.1007/978-3-319-48532-4_1},
abstract = {{Considering a variation of the classical Erd{\H{o}}s-Szekeres type
problems, we count the number of general 4-holes (not necessarily convex, empty 4-gons)
in squared Horton sets of size $\sqrt{n}\!\times\!\sqrt{n}$.
Improving on previous upper and lower bounds we
show that this number is $\Theta(n^2\log n)$, which constitutes
the currently best upper bound on minimizing the number of general
\mbox{$4$-holes} for any set of $n$ points in the plane.
To obtain the improved bounds, we prove a result of independent
interest. We show that $\sum_{d=1}^n \frac{\varphi(d)}{d^2} =
\Theta(\log n)$, where $\varphi(d)$ is Euler's phi-function, the
number of positive integers less than~$d$ which are relatively prime
to $d$. This arithmetic function is also called Euler's totient
function and plays a role in number theory and cryptography.}},
originalfile = {/geometry/cggg.bib}
}
@article{afhpruv-clcfc-18,
author = {Oswin Aichholzer and Ruy Fabila-Monroy and Ferran Hurtado
and Pablo Perez-Lantero and Andres J. Ruiz-Vargas and Jorge Urrutia and Birgit Vogtenhuber},
title = {{{Cross-sections of line configurations in {$R^3$} and $(d\!-\!2)$-flat configurations in {$R^d$}}}},
journal = {Computational Geometry: Theory and Applications},
volume = {77},
number = {},
pages = {51--61},
year = {2019},
note = {Special Issue of CCCG 2014},
issn = {0925-7721},
doi = {https://doi.org/10.1016/j.comgeo.2018.02.005},
url = {http://www.sciencedirect.com/science/article/pii/S0925772118300154},
abstract = {{We consider sets $\mathcal{L} = \{\ell_1, \ldots, \ell_n\}$ of $n$ labeled lines in general position in ${{\sf l} \kern -.10em {\sf R} }^3$, and
study the order types of point sets $\{p_1, \ldots, p_n\}$ that stem from the intersections of the lines in $\mathcal{L}$ with (directed) planes $\Pi$, not parallel to any line of $\mathcal{L}$, that is, the proper cross-sections of $\mathcal{L}$.
As two main results, we show that the number of different order types that can be obtained as cross-sections of $\mathcal{L}$ is $O(n^9)$ when considering all possible planes $\Pi$,
and $O(n^3)$ when restricting considerations to sets of pairwise parallel planes, where both bounds are tight.
The result for parallel planes implies that any set of $n$ points in ${{\sf l} \kern -.10em {\sf R} }^2$ moving with constant (but possibly different) speeds along straight lines forms at most $O(n^3)$ different order types over time.
We further generalize the setting from ${{\sf l} \kern -.10em {\sf R} }^3$ to ${{\sf l} \kern -.10em {\sf R} }^d$ with $d>3$, showing that the number of order types that can be obtained as cross-sections of a set of $n$ labeled $(d\!-\!2)$-flats in ${{\sf l} \kern -.10em {\sf R} }^d$ with planes is
$O\left(\dbinom{\binom{n}{3}+n}{d(d\!-\!2)}\right)$.}},
originalfile = {/geometry/cggg.bib}
}
@article{klmpsv-ddt-17,
title = {{{The dual diameter of triangulations}}},
journal = {Computational Geometry: Theory and Applications},
volume = {68},
pages = {243--252},
year = {2018},
note = {Special Issue in Memory of Ferran Hurtado},
issn = {0925-7721},
doi = {http://dx.doi.org/10.1016/j.comgeo.2017.06.008},
url = {http://www.sciencedirect.com/science/article/pii/S0925772117300603},
author = {Matias Korman and Stefan Langerman and Wolfgang Mulzer and Alexander Pilz and Maria Saumell and Birgit Vogtenhuber},
keywords = {Triangulation},
keywords = {Dual graph},
keywords = {Diameter},
keywords = {Optimization},
keywords = {Simple polygon},
abstract = {{Let $\mathcal{P}$ be a simple polygon with $n$ vertices.
The \emph{dual graph} $T^*$ of a triangulation~$T$ of~$\mathcal{P}$
is the graph whose vertices correspond to the bounded faces of
$T$ and whose edges connect those faces of~$T$ that share an edge.
We consider triangulations of~$\mathcal{P}$ that minimize or maximize the
diameter of their dual graph.
We show that both triangulations can be constructed in $O(n^3\log n)$ time
using dynamic programming.
If $\mathcal{P}$ is convex, we show that any minimizing triangulation has dual
diameter exactly $2\cdot\lceil\log_2(n/3)\rceil$ or
$2\cdot\lceil\log_2(n/3)\rceil -1$, depending on~$n$. Trivially, in this
case any maximizing triangulation has dual diameter $n-2$.
Furthermore, we investigate the relationship between the dual diameter
and the number of \emph{ears} (triangles with exactly two edges incident
to the boundary of $\mathcal{P}$) in a triangulation.
For convex $\mathcal{P}$, we show that there is always a triangulation that
simultaneously minimizes the dual diameter and maximizes the number of
ears.
In contrast, we give examples of general simple polygons where every
triangulation that maximizes the number of ears has dual diameter that
is quadratic in the minimum possible value.
We also consider the case of point sets in general position in the plane.
of~$T$ is defined as before.
We show that for any such set of $n$ points there are triangulations with
dual diameter in~$O(\log n)$ and in~$\Omega(\sqrt n)$.}},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{ahkprrrv-psst-16,
author = {Oswin Aichholzer and Thomas Hackl and Matias Korman and Alexander Pilz and G{\"u}nter Rote and Andr{\'e} van Renssen and Marcel Roeloffzen and Birgit Vogtenhuber},
title = {{{Packing Short Plane Spanning Trees in Complete Geometric Graphs}}},
booktitle = {27th International Symposium on Algorithms and Computation (ISAAC 2016)},
pages = {9:1--9:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
isbn = {978-3-95977-026-2},
issn = {1868-8969},
year = {2016},
volume = {64},
editor = {Seok-Hee Hong},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
url = {http://drops.dagstuhl.de/opus/volltexte/2016/6782},
urn = {urn:nbn:de:0030-drops-67823},
doi = {10.4230/LIPIcs.ISAAC.2016.9},
annote = {Keywords: Geometric Graphs, Graph Packing, Plane Graphs, Minimum Spanning Tree, Bottleneck Edge},
abstract = {Given a set of points in the plane, we want to establish a connection network between these points that consists of several disjoint layers. Motivated by sensor networks, we want that each layer is spanning and plane, and that no edge is very long (when compared to the minimum length needed to obtain a spanning graph). We consider two different approaches: first we show an almost optimal centralized approach to extract two graphs. Then we show a constant factor approximation for a distributed model in which each point can compute its adjacencies using only local information. In both cases the obtained layers are plane.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{ahvv-nng4h-15,
author = {O. Aichholzer and T.~Hackl and P.~Valtr and
B.~Vogtenhuber},
title = {{{A note on the number of general 4-holes in
perturbed grids}}},
booktitle = {Proc. $18^{th}$ Japan Conference on Discrete and
Computational Geometry and Graphs (JCDCG$^2$ 2015)},
pages = {68--69},
year = 2015,
address = {Kyoto, Japan},
category = {3b},
thackl_label = {49C},
xxarxiv = {},
xpdf = {/files/publications/geometry/ahvv-nng4h-15.pdf},
abstract = {Considering a variation of the classical Erd{\H{o}}s
and Szekeres type problems, we count the number of
general $4$-holes (empty \mbox{$4$-gons}) in the
$\sqrt{n}\!\times\!\sqrt{n}$ squared Horton
set. Improving on previous upper and lower bounds we
show that this number is $\Theta(n^2\log n)$, which
also constitutes the currently best upper bound on
minimizing the number of general \mbox{$4$-holes}
for any set of $n$ points in the plane.\\ To obtain
these bounds and as a result of independent
interest, we show that $\sum_{d=1}^n
\frac{\varphi(d)}{d^2} = \Theta(\log n)$, where
$\varphi(d)$ is Euler's phi-function, the number of
positive integers less than~$d$ which are relatively
prime to $d$.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{abhhhpv-rdtss-15,
author = {O. Aichholzer and T.~Biedl and T.~Hackl
and M.~Held and S.~Huber and P.~Palfrader and B.~Vogtenhuber},
title = {{{Representing Directed Trees as Straight Skeletons}}},
booktitle = {Proc. $23^{nd}$ International Symposium on Graph Drawing (GD 2015)},
series = {Lecture Notes in Computer Science (LNCS)},
volume = {9411},
nopublisher = {Springer, Heidelberg},
editor = {Emilio Di Giacomo and Anna Lubiw},
pages = {335--347},
year = 2015,
address = {Los Angeles, CA, USA},
category = {3b},
thackl_label = {48C},
arxiv = {1508.01076},
doi = {http://dx.doi.org/10.1007/978-3-319-27261-0},
isbn = {978-3-319-27260-3},
e-isbn = {978-3-319-27261-0},
issn = {0302-9743},
pdf = {/files/publications/geometry/abhhhpv-rdtss-15.pdf},
abstract = {The straight skeleton of a polygon is the geometric
graph obtained by tracing the vertices during a
mitered offsetting process. It is known that the
straight skeleton of a simple polygon is a tree, and
one can naturally derive directions on the edges of
the tree from the propagation of the shrinking
process.\\ In this paper, we ask the reverse
question: Given a tree with directed edges, can it
be the straight skeleton of a polygon? And if so,
can we find a suitable simple polygon? We answer
these questions for all directed trees where the
order of edges around each node is fixed.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{aafhpprsv-agdsc-15,
author = {B.M.~\'Abrego and O. Aichholzer and S.~Fern\'andez-Merchant and T.~Hackl
and J.~Pammer and A.~Pilz and P.~Ramos and G.~Salazar and B.~Vogtenhuber},
title = {{{All Good Drawings of Small Complete Graphs}}},
booktitle = {Proc. $31^{st}$ European Workshop on Computational
Geometry EuroCG '15},
pages = {57--60},
year = 2015,
address = {Ljubljana, Slovenia},
category = {3b},
thackl_label = {46C},
xxarxiv = {},
pdf = {/files/publications/geometry/aafhpprsv-agdsc-15.pdf},
abstract = {\emph{Good drawings} (also known as \emph{simple
topological graphs}) are drawings of graphs such
that any two edges intersect at most once. Such
drawings have attracted attention as generalizations
of geometric graphs, in connection with the crossing
number, and as data structures in their own right.
We are in particular interested in good drawings of
the complete graph. In this extended abstract, we
describe our techniques for generating all different
weak isomorphism classes of good drawings of the
complete graph for up to nine vertices. In
addition, all isomorphism classes were enumerated.
As an application of the obtained data, we present
several existential and extremal properties of these
drawings.},
originalfile = {/geometry/cggg.bib}
}
@article{aahhpruvv-kcps-14,
author = {O. Aichholzer and F.~Aurenhammer and T.~Hackl and
F.~Hurtado and A.~Pilz and P.~Ramos and J.~Urrutia and P.~Valtr and B.~Vogtenhuber},
title = {{{On $k$-Convex Point Sets}}},
journal = {Computational Geometry: Theory and Applications},
year = 2014,
volume = {47},
number = {8},
pages = {809--832},
thackl_label = {40J},
category = {3a},
issn = {0925-7721},
url = {http://www.sciencedirect.com/science/article/pii/S0925772114000534},
doi = {http://dx.doi.org/10.1016/j.comgeo.2014.04.004},
pdf = {/files/publications/geometry/aahhpruvv-kcps-14.pdf},
abstract = {We extend the (recently introduced) notion of
$k$-convexity of a two-di\-men\-sional subset of the
Euclidean plane to finite point sets. A set of $n$
points is considered $k$-convex if there exists a
spanning (simple) polygonization such that the
intersection of any straight line with its interior
consists of at most~$k$ disjoint intervals. As the
main combinatorial result, we show that every
$n$-point set contains a subset of $\Omega(\log^2
n)$ points that are in 2-convex position. This
bound is asymptotically tight. From an algorithmic
point of view, we show that 2-convexity of a finite
point set can be decided in polynomial time, whereas
the corresponding problem on $k$-convexity becomes
NP-complete for any fixed $k\geq 3$.},
originalfile = {/geometry/cggg.bib}
}
@article{ahplmv-mseup-15,
author = {O. Aichholzer and T.~Hackl
and S.~Lutteropp and T.~Mchedlidze and A.~Pilz and B.~Vogtenhuber},
title = {{{Monotone Simultaneous Embedding of Upward Planar Digraphs}}},
journal = {Journal of Graph Algorithms and Applications},
year = 2015,
volume = {19},
number = {1},
pages = {87--110},
thackl_label = {39J},
category = {3a},
issn = {1526-1719},
doi = {http://dx.doi.org/10.7155/jgaa.00350},
arxiv = {1310.6955v2},
pdf = {/files/publications/geometry/ahplmv-mseup-15.pdf},
abstract = {We study monotone simultaneous embeddings of upward
planar digraphs, which are simultaneous embeddings
where the drawing of each digraph is upward planar,
and the directions of the upwardness of different
graphs can differ. We first consider the special
case where each digraph is a directed path. In
contrast to the known result that any two directed
paths admit a monotone simultaneous embedding, there
exist examples of three paths that do not admit such
an embedding for any possible choice of directions
of monotonicity.\\ We prove that if a monotone
simultaneous embedding of three paths exists then it
also exists for any possible choice of directions of
monotonicity. We provide a polynomial-time
algorithm that, given three paths, decides whether a
monotone simultaneous embedding exists and, in the
case of existence, also constructs such an
embedding. On the other hand, we show that already
for three paths, any monotone simultaneous embedding
might need a grid whose size is exponential in the
number of vertices. For more than three paths, we
present a polynomial-time algorithm that, given any
number of paths and predefined directions of
monotonicity, decides whether the paths admit a
monotone simultaneous embedding with respect to the
given directions, including the construction of a
solution if it exists. Further, we show several
implications of our results on monotone simultaneous
embeddings of general upward planar digraphs.
Finally, we discuss complexity issues related to our
problems.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{ahplmv-msedp-14,
author = {O. Aichholzer and T.~Hackl
and S.~Lutteropp and T.~Mchedlidze and A.~Pilz and B.~Vogtenhuber},
title = {{{Monotone Simultaneous Embedding of Directed Paths}}},
booktitle = {Proc. $30^{th}$ European Workshop on Computational
Geometry EuroCG '14},
pages = {online},
year = 2014,
address = {Dead Sea, Israel},
category = {3b},
thackl_label = {39C},
arxiv = {1310.6955v2},
pdf = {/files/publications/geometry/ahplmv-msedp-14.pdf},
abstract = {We consider a variant of monotone simultaneous
embeddings (MSEs) of directed graphs where all
graphs are directed paths and have distinct
directions of monotonicity. In contrast to the
known result that any two directed paths admit an
MSE, there exist examples of three paths that do not
admit such an embedding for any possible choice of
directions of monotonicity. We prove that if an MSE
of three paths exists then it also exists for any
possible choice of directions of monotonicity. We
provide a polynomial-time algorithm that, given
three paths, decides whether an MSE exists.
Finally, we provide a polynomial-time algorithm that
answers the existence question for any given number
of paths and predefined directions of monotonicity.},
originalfile = {/geometry/cggg.bib}
}
@article{ahkpv-gpps-14,
author = {O. Aichholzer and T.~Hackl and M.~Korman and A.~Pilz and
B.~Vogtenhuber},
title = {{{Geodesic-preserving polygon simplification}}},
journal = {Int'l Journal of Computational Geometry \& Applications},
year = 2014,
volume = {24},
category = {3a},
number = {4},
oaich_label = {},
thackl_label = {38J},
pages = {307--323},
pdf = {/files/publications/geometry/ahkpv-gpps-13.pdf},
doi = {http://dx.doi.org/10.1142/S0218195914600097},
arxiv = {1309.3858},
abstract = {Polygons are a paramount data structure in computational
geometry. While the complexity of many algorithms on simple
polygons or polygons with holes depends on the size of the
input polygon, the intrinsic complexity of the problems
these algorithms solve is often related to the reflex
vertices of the polygon. In this paper, we give an
easy-to-describe linear-time method to replace an input
polygon~$P$ by a polygon $P'$ such that (1)~$P'$
contains~$P$, (2)~$P'$ has its reflex vertices at the same
positions as~$P$, and (3)~the number of vertices of $P'$ is
linear in the number of reflex vertices. Since the
solutions of numerous problems on polygons (including
shortest paths, geodesic hulls, separating point sets, and
Voronoi diagrams) are equivalent for both $P$ and $P'$, our
algorithm can be used as a preprocessing step for several
algorithms and makes their running time dependent on the
number of reflex vertices rather than on the size of~$P$.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{ahkpv-gpps-13,
author = {O. Aichholzer and T.~Hackl and M.~Korman and A.~Pilz and
B.~Vogtenhuber},
title = {{{Geodesic-preserving polygon simplification}}},
booktitle = {Lecture Notes in Computer Science (LNCS), Proc. $24^{th}$ Int. Symp.
Algorithms and Computation (ISAAC 2013)},
pages = {11--21},
year = {2013},
volume = {8283},
address = {Hong Kong, China},
publisher = {Springer Verlag},
category = {3b},
pdf = {/files/publications/geometry/ahkpv-gpps-13.pdf},
thackl_label = {38C},
arxiv = {1309.3858},
abstract = {Polygons are a paramount data structure in computational
geometry. While the complexity of many algorithms on simple
polygons or polygons with holes depends on the size of the
input polygon, the intrinsic complexity of the problems
these algorithms solve is often related to the reflex
vertices of the polygon. In this paper, we give an
easy-to-describe linear-time method to replace an input
polygon~$P$ by a polygon $P'$ such that (1)~$P'$
contains~$P$, (2)~$P'$ has its reflex vertices at the same
positions as~$P$, and (3)~the number of vertices of $P'$ is
linear in the number of reflex vertices. Since the
solutions of numerous problems on polygons (including
shortest paths, geodesic hulls, separating point sets, and
Voronoi diagrams) are equivalent for both $P$ and $P'$, our
algorithm can be used as a preprocessing step for several
algorithms and makes their running time dependent on the
number of reflex vertices rather than on the size of~$P$.},
originalfile = {/geometry/cggg.bib}
}
@article{achhkpsuvw-cpmbl-13a,
author = {O. Aichholzer and J.~Cardinal and T.~Hackl and F.~Hurtado
and M.~Korman and A.~Pilz and R.I.~Silveira and R.~Uehara
and B.~Vogtenhuber and E.~Welzl},
title = {{{Cell-Paths in Mono- and Bichromatic Line
Arrangements in the Plane}}},
journal = {Discrete Mathematics \& Theoretical Computer Science
(DMTCS)},
category = {3a},
oaich_label = {},
thackl_label = {35J},
pages = {317--332},
volume = {16},
number = {3},
year = 2014,
pdf = {/files/publications/geometry/achhkpsuvw-cpmbl-13.pdf},
url = {https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/2590.1.html},
xdoi = {http://dx.doi.org/...},
abstract = {We show that in every arrangement of $n$ red and blue
lines (in general position and not all of the same color)
there is a path through a linear number of cells where red
and blue lines are crossed alternatingly (and no cell is
revisited). When all lines have the same color, and hence
the preceding alternating constraint is dropped, we prove
that the dual graph of the arrangement always contains a
path of length $\Theta(n^2)$.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{achhkpsuvw-cpmbl-13,
author = {O. Aichholzer and J.~Cardinal and T.~Hackl and F.~Hurtado
and M.~Korman and A.~Pilz and R.I.~Silveira and R.~Uehara
and B.~Vogtenhuber and E.~Welzl},
title = {{{Cell-Paths in Mono- and Bichromatic Line
Arrangements in the Plane}}},
booktitle = {Proc. $25^{th}$ Annual Canadian Conference on
Computational Geometry CCCG 2013},
pages = {169--174},
year = 2013,
address = {Waterloo, Ontario, Canada},
category = {3b},
thackl_label = {35C},
pdf = {/files/publications/geometry/achhkpsuvw-cpmbl-13.pdf},
abstract = {We show that in every arrangement of $n$ red and blue
lines (in general position and not all of the same color)
there is a path through a linear number of cells where red
and blue lines are crossed alternatingly (and no cell is
revisited). When all lines have the same color, and hence
the preceding alternating constraint is dropped, we prove
that the dual graph of the arrangement always contains a
path of length $\Theta(n^2)$.},
originalfile = {/geometry/cggg.bib}
}
@article{ahprsv-etgdc-15,
author = {O.~Aichholzer and T.~Hackl and A.~Pilz and P.~Ramos and
V.~Sacrist\'{a}n and B.~Vogtenhuber},
title = {{{Empty triangles in good drawings of the complete graph}}},
journal = {Graphs and Combinatorics},
issn = {0911-0119},
publisher = {Springer Japan},
pages = {335--345},
volume = {31},
number = {2},
htmlnote = {For
Springer Online First.},
doi = {http://dx.doi.org/10.1007/s00373-015-1550-5},
year = 2015,
thackl_label = {34J},
category = {3a},
pdf = {/files/publications/geometry/ahprsv-etgdc-13.pdf},
eprint = {1306.5081},
archiveprefix = {arXiv},
keywords = {Good drawings; Empty triangles; Erdős–Szekeres type problems},
abstract = {A good drawing of a simple graph is a drawing on the
sphere or, equivalently, in the plane in which vertices are
drawn as distinct points, edges are drawn as Jordan arcs
connecting their end vertices, and any pair of edges
intersects at most once. In any good drawing, the edges of
three pairwise connected vertices form a Jordan curve which
we call a triangle. We say that a triangle is empty if one
of the two connected components it induces does not contain
any of the remaining vertices of the drawing of the graph.
We show that the number of empty triangles in any good
drawing of the complete graph $K_n$ with $n$ vertices is at
least $n$.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{ahprsv-etgdc-13,
author = {O.~Aichholzer and T.~Hackl and A.~Pilz and P.~Ramos and
V.~Sacrist\'{a}n and B.~Vogtenhuber},
title = {{{Empty triangles in good drawings of the complete graph}}},
booktitle = {Mexican Conference on Discrete Mathematics and
Computational Geometry},
pages = {21--29},
year = 2013,
address = {Oaxaca, M{\'e}xico},
thackl_label = {34C},
category = {3b},
pdf = {/files/publications/geometry/ahprsv-etgdc-13.pdf},
eprint = {1306.5081},
abstract = {A good drawing of a simple graph is a drawing on the
sphere or, equivalently, in the plane in which vertices are
drawn as distinct points, edges are drawn as Jordan arcs
connecting their end vertices, and any pair of edges
intersects at most once. In any good drawing, the edges of
three pairwise connected vertices form a Jordan curve which
we call a triangle. We say that a triangle is empty if one
of the two connected components it induces does not contain
any of the remaining vertices of the drawing of the graph.
We show that the number of empty triangles in any good
drawing of the complete graph $K_n$ with $n$ vertices is at
least $n$.},
originalfile = {/geometry/cggg.bib}
}
@article{ahopsv-fcppt-14,
author = {O.~Aichholzer and T.~Hackl and D.~Orden and A.~Pilz and
M.~Saumell and B.~Vogtenhuber},
title = {{{Flips in combinatorial pointed
pseudo-triangulations with face degree at most four}}},
journal = {Int'l Journal of Computational Geometry \& Applications},
year = 2014,
volume = {24},
number = {3},
pages = {197--224},
thackl_label = {33J},
category = {3a},
issn = {0218-1959},
online-issn = {1793-6357},
doi = {http://dx.doi.org/10.1142/S0218195914600036},
eprint = {1310.0833},
archiveprefix = {arXiv},
pdf = {/files/publications/geometry/ahopsv-fcppt-14.pdf},
abstract = {In this paper we consider the flip operation for
combinatorial pointed pseudo-triangulations where faces
have size~3 or~4, so-called \emph{combinatorial 4-PPTs}. We
show that every combinatorial 4-PPT is stretchable to a
geometric pseudo-triangulation, which in general is not the
case if faces may have size larger than 4. Moreover, we
prove that the flip graph of combinatorial 4-PPTs with
triangular outer face is connected and has dia\/meter
$O(n^2)$.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{ahopsv-fcppt-13,
author = {O.~Aichholzer and T.~Hackl and D.~Orden and A.~Pilz and
M.~Saumell and B.~Vogtenhuber},
title = {{{Flips in combinatorial pointed
pseudo-triangulations with face degree at most four
(extended abstract)}}},
booktitle = {Proc. $15^{th}$ Spanish Meeting on Computational Geometry
2013},
pages = {131--134},
year = 2013,
address = {Sevilla, Spain},
thackl_label = {33C},
category = {3b},
eprint = {1310.0833},
pdf = {/files/publications/geometry/ahopsv-fcppt-13.pdf},
abstract = {In this paper we consider the flip operation for
combinatorial pointed pseudo-triangulations where faces
have size~3 or~4, so-called \emph{combinatorial 4-PPTs}. We
show that every combinatorial 4-PPT is stretchable to a
geometric pseudo-triangulation, which in general is not the
case if faces may have size larger than 4. Moreover, we
prove that the flip graph of combinatorial 4-PPTs with
triangular outer face is connected and has dia\/meter
$O(n^2)$.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{ahsvw-sdala-13,
author = {O.~Aichholzer and T.~Hackl and V.~Sacrist\'{a}n and
B.~Vogtenhuber and R.~Wallner},
title = {{{Simulating distributed algorithms for lattice agents}}},
booktitle = {Proc. $15^{th}$ Spanish Meeting on Computational Geometry
2013},
pages = {81--84},
year = 2013,
address = {Sevilla, Spain},
thackl_label = {32C},
category = {3b},
pdf = {/files/publications/geometry/ahsvw-sdala-13.pdf},
htmlnote = {Link
to simulators page},
abstract = {We present a practical Java tool for simulating
synchronized distributed algorithms on sets of 2- and
3-dimensional square/cubic lattice-based agents. This
\emph{AgentSystem} assumes that each agent is capable to
change position in the lattice and that neighboring agents
can attach and detach from each other. In addition, it
assumes that each module has some constant size memory and
computation capability, and can send/receive constant size
messages to/from its neighbors. The system allows the user
to define sets of agents and sets of rules and apply one to
the other. The \emph{AgentSystem} simulates the
synchronized execution of the set of rules by all the
modules, and can keep track of all actions made by the
modules at each step, supporting consistency warnings and
error checking. Our intention is to provide a useful tool
for the researchers from geometric distributed algorithms.},
originalfile = {/geometry/cggg.bib}
}
@article{afhhpv-lbnsc-14,
author = {O. Aichholzer and R.~Fabila-Monroy and T.~Hackl and
C.~Huemer and A.~Pilz and B.~Vogtenhuber},
title = {{{Lower bounds for the number of small convex $k$-holes}}},
journal = {Computational Geometry: Theory and Applications},
year = 2014,
volume = {47},
number = {5},
pages = {605--613},
thackl_label = {31J},
category = {3a},
doi = {http://dx.doi.org/10.1016/j.comgeo.2013.12.002},
pdf = {/files/publications/geometry/afhhpv-lbnsc-13-cgta.pdf},
abstract = {Let $S$ be a set of $n$ points in the plane in general
position, that is, no three points of $S$ are on a line. We
consider an Erd{\H{o}}s-type question on the least number
$h_k(n)$ of convex \mbox{$k$-holes} in $S$, and give
improved lower bounds on $h_k(n)$, for $3\leq k\leq 5$.
Specifically, we show that $h_{3}(n) \geq n^2 -
\frac{32n}{7} + \frac{22}{7}$, $h_{4}(n) \geq \frac{n^2}{2}
- \frac{9n}{4} - o(n)$, and $h_5(n) \geq \frac{3n}{4} -
o(n)$. We further settle several questions on sets of 12
points posed by Dehnhardt in 1987.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{afhhpv-lbnsc-12,
author = {O. Aichholzer and R.~Fabila-Monroy and T.~Hackl and
C.~Huemer and A.~Pilz and B.~Vogtenhuber},
title = {{{Lower bounds for the number of small convex $k$-holes}}},
booktitle = {Proc. $24^{th}$ Annual Canadian Conference on
Computational Geometry CCCG 2012},
pages = {247--252},
year = 2012,
address = {Charlottetown, PEI, Canada},
category = {3b},
thackl_label = {31C},
pdf = {/files/publications/geometry/afhhpv-lbnsc-12-cccg.pdf},
abstract = {Let $S$ be a set of $n$ points in the plane in general
position, that is, no three points of $S$ are on a line. We
consider an Erd{\H{o}}s-type question on the least number
$h_k(n)$ of convex \mbox{$k$-holes} in $S$, and give
improved lower bounds on $h_k(n)$, for $3\leq k\leq 5$.
Specifically, we show that $h_{3}(n) \geq n^2 -
\frac{32n}{7} + \frac{22}{7}$, $h_{4}(n) \geq \frac{n^2}{2}
- \frac{9n}{4} - o(n)$, and $h_5(n) \geq \frac{3n}{4} - o(n)$.},
originalfile = {/geometry/cggg.bib}
}
@article{afghhhuvv-okkps-15,
author = {Oswin Aichholzer and Ruy Fabila-Monroy and Hernan
Gonzalez-Aguilar and Thomas Hackl and Marco A. Heredia and
Clemens Huemer and Jorge Urrutia and Pavel Valtr and Birgit
Vogtenhuber},
title = {{{On $k$-Gons and $k$-Holes in Point Sets}}},
journal = {Computational Geometry: Theory and Applications},
year = 2015,
volume = {48},
number = {7},
pages = {528--537},
category = {3a},
thackl_label = {29J},
arxiv = {1409.0081},
doi = {http://dx.doi.org/10.1016/j.comgeo.2014.12.007},
pdf = {/files/publications/geometry/afghhhuvv-okkps-15.pdf},
abstract = {We consider a variation of the classical
Erd{\H{o}}os-Szekeres problems on the existence and number of
convex $k$-gons and $k$-holes (empty $k$-gons) in a set of
$n$ points in the plane. Allowing the $k$-gons to be
non-convex, we show bounds and structural results on
maximizing and minimizing their numbers. Most noteworthy,
for any $k$ and sufficiently large $n$, we give a quadratic
lower bound for the number of $k$-holes, and show that this
number is maximized by sets in convex position. We also
provide an improved lower bound for the number of convex
6-holes.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{afghhhuvv-okkps-11,
author = {Oswin Aichholzer and Ruy Fabila-Monroy and Hernan
Gonzalez-Aguilar and Thomas Hackl and Marco A. Heredia and
Clemens Huemer and Jorge Urrutia and Pavel Valtr and Birgit
Vogtenhuber},
title = {{{On $k$-Gons and $k$-Holes in Point Sets}}},
booktitle = {Proc. $23^{rd}$ Annual Canadian Conference on
Computational Geometry CCCG 2011},
pages = {21--26},
year = 2011,
address = {Toronto, Canada},
category = {3b},
thackl_label = {29C},
pdf = {/files/publications/geometry/afghhhuvv-okkps-11.pdf},
abstract = {We consider a variation of the classical
Erd{\H{o}}os-Szekeres problems on the existence and number of
convex $k$-gons and $k$-holes (empty $k$-gons) in a set of
$n$ points in the plane. Allowing the $k$-gons to be
non-convex, we show bounds and structural results on
maximizing and minimizing their numbers. Most noteworthy,
for any $k$ and sufficiently large $n$, we give a quadratic
lower bound for the number of $k$-holes, and show that this
number is maximized by sets in convex position. We also
provide an improved lower bound for the number of convex
6-holes.},
originalfile = {/geometry/cggg.bib}
}
@incollection{ahv-5g5h-12,
author = {O. Aichholzer and T. Hackl and B. Vogtenhuber},
title = {{{On 5-{G}ons and 5-{H}oles}}},
volume = {7579},
issue = {},
editor = {A.~Marquez and P.~Ramos and J.~Urrutia},
booktitle = {Computational Geometry: XIV Spanish Meeting on
Computational Geometry, EGC 2011, Festschrift
Dedicated to Ferran Hurtado on the Occasion of His
60th Birthday, Alcal{\'a} de Henares, Spain, June 27-30,
2011, Revised Selected Papers},
xxbooktitle = {Special issue: XIV Encuentros de Geometr\'{\i}a
Computacional ECG2011},
series = {Lecture Notes in Computer Science (LNCS)},
category = {3a},
thackl_label = {28J},
pdf = {/files/publications/geometry/ahv-5g5h-12.pdf},
pages = {1--13},
year = 2012,
publisher = {Springer},
abstract = {We consider an extension of a question of Erd{\H{o}}s on the
number of $k$-gons in a set of $n$ points in the plane.
Relaxing the convexity restriction we obtain results on
5-gons and 5-holes (empty 5-gons). In particular, we show a
direct relation between the number of non-convex 5-gons and
the rectilinear crossing number, provide an improved lower
bound for the number of convex 5-holes any point set must
contain, and prove that the number of general 5-holes is
asymptotically maximized for point sets in convex
position.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{ahv-o5g5h-11,
author = {O. Aichholzer and T. Hackl and B. Vogtenhuber},
title = {{{On 5-gons and 5-holes}}},
booktitle = {Proc. XIV Encuentros de Geometr\'{\i}a Computacional},
category = {3b},
thackl_label = {28C},
pages = {7--10},
pdf = {/files/publications/geometry/ahv-o5g5h-11.pdf},
year = 2011,
address = {Alcal\'a, Spain},
abstract = {We consider an extention of a question of Erd{\H{o}}s on the
number of $k$-gons in a set of $n$ points in the plane.
Relaxing the convexity restriction we obtain results on
5-gons and 5-holes (empty 5-gons).},
originalfile = {/geometry/cggg.bib}
}
@article{afghhhuv-4hps-14,
author = {O.~Aichholzer and R.~Fabila-Monroy and
H.~Gonz{\'a}lez-Aguilar and T.~Hackl and M.A.~Heredia and
C.~Huemer and J.~Urrutia and B.~Vogtenhuber},
title = {{{\mbox{4-Holes} in Point Sets}}},
journal = {Computational Geometry: Theory and Applications},
note = {Special Issue on the 27th European Workshop on Computational Geometry (EuroCG 2011)},
year = 2014,
volume = {47},
number = {6},
pages = {644--650},
thackl_label = {27J},
category = {3a},
pdf = {/files/publications/geometry/afghhhuv-4hps-14.pdf},
doi = {http://dx.doi.org/10.1016/j.comgeo.2013.12.004},
abstract = {We consider a variant of a question of Erd{\H{o}}s on the
number of empty $k$-gons ($k$-holes) in a set of $n$ points
in the plane, where we allow the $k$-gons to be non-convex.
We show bounds and structural results on maximizing and
minimizing the number of general 4-holes, and maximizing
the number of non-convex 4-holes. In particular, we show
that for $n\geq 9$, the maximum number of general 4-holes
is ${n \choose 4}$, the minimum number of general 4-holes
is at least $\frac{5}{2}n^2 - \Theta(n)$, and the maximum
number of non-convex 4-holes is at least
$\frac{1}{2}n^3-\Theta(n^2\log n)$ and at most
$\frac{1}{2}n^3-\Theta(n^2)$.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{afghhhuv-4hps-11,
author = {O.~Aichholzer and R.~Fabila-Monroy and
H.~Gonz{\'a}lez-Aguilar and T.~Hackl and M.A.~Heredia and
C.~Huemer and J.~Urrutia and B.~Vogtenhuber},
title = {{{\mbox{4-Holes} in Point Sets}}},
booktitle = {Proc. $27^{th}$ European Workshop on Computational
Geometry EuroCG '11},
pages = {115--118},
year = 2011,
address = {Morschach, Switzerland},
thackl_label = {27C},
category = {3b},
pdf = {/files/publications/geometry/afghhhuv-4hps-11.pdf},
abstract = {We consider a variant of a question of Erd{\H{o}}s on the
number of empty $k$-gons ($k$-holes) in a set of $n$ points
in the plane, where we allow the $k$-gons to be non-convex.
We show bounds and structural results on maximizing and
minimizing the number of general \mbox{4-holes}, and
maximizing the number of non-convex \mbox{4-holes}.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{ahv-cppt-10,
author = {O. Aichholzer and T.~Hackl and B.~Vogtenhuber},
title = {{{Compatible Pointed Pseudo-Triangulations}}},
booktitle = {Proc. $22^{nd}$ Annual Canadian Conference on
Computational Geometry CCCG 2010},
pages = {91--94},
year = 2010,
address = {Winnipeg, Manitoba, Canada},
category = {3b},
thackl_label = {24C},
pdf = {/files/publications/geometry/ahv-cppt-10.pdf},
abstract = {For a given point set $S$ (in general position), two
pointed pseudo-triangulations are compatible if their union
is plane. We show that for any set $S$ there exist two
maximally disjoint compatible pointed
pseudo-triangulations, that is, their union is a
triangulation of~$S$. In contrast, we show that there are
point sets~$S$ and pointed pseudo-triangulations~$T$ such
that there exists no pointed pseudo-triangulation that is
compatible to and different from~$T$.},
originalfile = {/geometry/cggg.bib}
}
@article{afhkprv-bdt-12,
author = {O. Aichholzer and R.~Fabila-Monroy and T.~Hackl and M.~van
Kreveld and A.~Pilz and P.~Ramos and B.~Vogtenhuber},
title = {{{Blocking Delaunay Triangulations}}},
year = 2013,
volume = {46},
number = {2},
journal = {Computational Geometry: Theory and Applications},
pages = {154--159},
category = {3a},
oaich_label = {},
thackl_label = {23J},
doi = {http://dx.doi.org/10.1016/j.comgeo.2012.02.005},
pmcid = {3587385},
pmcurl = {http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3587385/},
pdf = {/files/publications/geometry/afhkprv-bdt-13.pdf},
abstract = {Given a set $B$ of $n$ blue points in general position, we
say that a set of red points $R$ blocks $B$ if in the
Delaunay triangulation of $B\cup R$ there is no edge
connecting two blue points. We give the following bounds
for the size of the smallest set $R$ blocking $B$:
(i)~$3n/2$ red points are always sufficient to block a set
of $n$ blue points, (ii)~if $B$ is in convex position,
$5n/4$ red points are always sufficient to block it, and
(iii)~at least $n-1$ red points are always necessary, and
there exist sets of blue points that require at least $n$
red points to be blocked.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{afhkprv-bdt-10,
author = {O. Aichholzer and R.~Fabila-Monroy and T.~Hackl and M.~van
Kreveld and A.~Pilz and P.~Ramos and B.~Vogtenhuber},
title = {{{Blocking Delaunay Triangulations}}},
booktitle = {Proc. $22^{nd}$ Annual Canadian Conference on
Computational Geometry CCCG 2010},
pages = {21--24},
year = 2010,
address = {Winnipeg, Manitoba, Canada},
category = {3b},
thackl_label = {23C},
pdf = {/files/publications/geometry/afhkprv-bdt-10.pdf},
abstract = {Given a set $B$ of $n$ blue points in general position, we
say that a set of red points $R$ blocks $B$ if in the
Delaunay triangulation of $B\cup R$ there is no edge
connecting two blue points. We give the following bounds
for the size of the smallest set $R$ blocking $B$:
(i)~$3n/2$ red points are always sufficient to block a set
of $n$ blue points, (ii)~if $B$ is in convex position,
$5n/4$ red points are always sufficient to block it, and
(iii)~at least $n-1$ red points are always necessary, and
there exist sets of blue points that require at least $n$
red points to be blocked.},
originalfile = {/geometry/cggg.bib}
}
@article{aahhpv-3cpt-15,
author = {O.~Aichholzer and F.~Aurenhammer and T. Hackl and
C.~Huemer and A.~Pilz and B.~Vogtenhuber},
title = {{{\mbox{3-Colorability} of Pseudo-Triangulations}}},
journal = {Int'l Journal of Computational Geometry \& Applications},
year = 2015,
volume = {25},
category = {3a},
number = {4},
oaich_label = {},
thackl_label = {22J},
pages = {283-298},
pdf = {/files/publications/geometry/aahhpv-3cpt-10.pdf},
doi = {http://dx.doi.org/10.1142/S0218195915500168},
xarxiv = {},
abstract = {Deciding $3$-colorability for general plane graphs is
known to be an NP-complete problem. However, for certain
classes of plane graphs, like triangulations, polynomial
time algorithms exist. We consider the family of
pseudo-triangulations (a generalization of triangulations)
and prove NP-completeness for this class, even if the
maximum face-degree is bounded to four, or pointed
pseudo-triangulations with maximum face degree five are
considered. As a complementary result, we show that for
pointed pseudo-triangulations with maximum face-degree
four, a $3$-coloring always exists and can be found in
linear time.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{aahhpv-3cpt-10,
author = {O.~Aichholzer and F.~Aurenhammer and T. Hackl and
C.~Huemer and A.~Pilz and B.~Vogtenhuber},
title = {{{\mbox{3-Colorability} of Pseudo-Triangulations}}},
booktitle = {Proc. $26^{th}$ European Workshop on Computational
Geometry EuroCG '10},
pages = {21--24},
year = 2010,
address = {Dortmund, Germany},
thackl_label = {22C},
pdf = {/files/publications/geometry/aahhpv-3cpt-10.pdf},
abstract = {Deciding $3$-colorability for general plane graphs is
known to be an NP-complete problem. However, for certain
classes of plane graphs, like triangulations, polynomial
time algorithms exist. We consider the family of
pseudo-triangulations (a generalization of triangulations)
and prove NP-completeness for this class, even if the
maximum face-degree is bounded to four, or pointed
pseudo-triangulations with maximum face degree five are
considered. As a complementary result, we show that for
pointed pseudo-triangulations with maximum face-degree
four, a $3$-coloring always exists and can be found in
linear time.},
originalfile = {/geometry/cggg.bib}
}
@article{ahhprsv-pgpc-10,
author = {O. Aichholzer and T. Hackl and M. Hoffmann and A.~Pilz and
G.~Rote and B.~Speckmann and B.~Vogtenhuber},
title = {{{Plane graphs with parity constraints}}},
year = 2014,
volume = {30},
number = {1},
category = {3a},
journal = {Graphs and Combinatorics},
pdf = {/files/publications/geometry/ahhprsv-pgpc-12.pdf},
thackl_label = {20J},
pages = {47--69},
publisher = {Springer},
htmlnote = {For
Springer Online First.},
doi = {http://dx.doi.org/10.1007/s00373-012-1247-y},
abstract = {Let $S$ be a set of $n$ points in general position in the
plane. Together with $S$ we are given a set of parity
constraints, that is, every point of $S$ is labeled either
even or odd. A graph $G$ on $S$ satisfies the parity
constraint of a point $p \in S$, if the parity of the
degree of $p$ in $G$ matches its label. In this paper we
study how well various classes of planar graphs can satisfy
arbitrary parity constraints. Specifically, we show that we
can always find a plane tree, a two-connected outerplanar
graph, or a pointed pseudo-triangulation which satisfy all
but at most three parity constraints. With triangulations
we can satisfy about 2/3 of all parity constraints. In
contrast, for a given simple polygon $H$ with polygonal
holes on $S$, we show that it is NP-complete to decide
whether there exists a triangulation of $H$ that satisfies
all parity constraints.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{ahhprsv-pgpc-09,
author = {O. Aichholzer and T. Hackl and M.~Hoffmann and A.~Pilz and
G.~Rote and B.~Speckmann and B.~Vogtenhuber},
title = {{{Plane Graphs with Parity Constraints}}},
pdf = {/files/publications/geometry/ahhprsv-pgpc-09.pdf},
oaich_label = {83},
thackl_label = {20C},
booktitle = {Lecture Notes in Computer Science (LNCS), Proc. $11^{th}$
International Workshop on Algorithms and Data Structures
(WADS)},
volume = {5664},
address = {Banff, Alberta, Canada},
pages = {13--24},
year = 2009,
abstract = {Let $S$ be a set of $n$ points in general position in the
plane. Together with $S$ we are given a set of parity
constraints, that is, every point of $S$ is labeled either
even or odd. A graph $G$ on $S$ satisfies the parity
constraint of a point $p \in S$, if the parity of the
degree of $p$ in $G$ matches its label. In this paper we
study how well various classes of planar graphs can satisfy
arbitrary parity constraints. Specifically, we show that we
can always find a plane tree, a two-connected outerplanar
graph, or a pointed pseudo-triangulation which satisfy all
but at most three parity constraints. With triangulations
we can satisfy about 2/3 of all parity constraints. In
contrast, for a given simple polygon $H$ with polygonal
holes on $S$, we show that it is NP-complete to decide
whether there exists a triangulation of $H$ that satisfies
all parity constraints.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{aadhtv-lubne-09,
author = {O. Aichholzer and F. Aurenhammer and O.~Devillers and
T.~Hackl and M.~Teillaud and B.~Vogtenhuber},
title = {{{Lower and upper bounds on the number of empty
cylinders and ellipsoids}}},
booktitle = {Proc. $25^{th}$ European Workshop on Computational
Geometry EuroCG '09},
category = {3b},
pages = {139--142},
pdf = {/files/publications/geometry/aadhtv-lubne-09.pdf},
oaich_label = {79},
thackl_label = {18C},
year = 2009,
address = {Brussels, Belgium},
htmlnote = {Also available as Research Report RR-6748 "Counting
Quadrics and Delaunay Triangulations and a new Convex Hull
Theorem", INRIA, 2008, at
http://hal.inria.fr/inria-00343651.},
abstract = {Given a set $\cal S$ of $n$ points in three dimensions, we
study the maximum numbers of quadrics spanned by subsets of
points in $\cal S$ in various ways. Among various results
we prove that the number of empty circular cylinders is
between $\Omega(n^3)$ and $O(n^4)$ while we have a tight
bound $\Theta(n^4)$ for empty ellipsoids. We also take
interest in pairs of empty homothetic ellipsoids, with
application to the number of combinatorially distinct
Delaunay triangulations obtained by orthogonal projections
of $\cal S$ on a two-dimensional plane, which is
$\Omega(n^4)$ and $O(n^5)$.
A side result is that the convex hull in $d$ dimensions of
a set of $n$ points, where one half lies in a subspace of
odd dimension~\mbox{$\delta > \frac{d}{2}$}, and the second
half is the (multi-dimensional) projection of the first
half on another subspace of dimension~$\delta$, has
complexity only $O\left(n^{\frac{d}{2}-1}\right)$.},
originalfile = {/geometry/cggg.bib}
}
@article{ahhhv-lbpsa-09b,
author = {O.~Aichholzer and T.~Hackl and C.~Huemer and F.~Hurtado
and B.~Vogtenhuber},
title = {{{Large bichromatic point sets admit empty monochromatic $4$-gons}}},
year = 2010,
journal = {SIAM Journal on Discrete Mathematics (SIDMA)},
volume = {23},
number = {4},
pages = {2147--2155},
category = {3a},
doi = {http://dx.doi.org/10.1137/090767947},
oaich_label = {78b},
thackl_label = {17J},
pdf = {/files/publications/geometry/ahhhv-lbpsa-09b.pdf},
abstract = {We consider a variation of a problem stated by {Erd\"os}
and Szekeres in 1935 about the existence of a number
$f^\textrm{ES}(k)$ such that any set $S$ of at least
$f^\textrm{ES}(k)$ points in general position in the plane
has a subset of $k$ points that are the vertices of a
convex $k$-gon. In our setting the points of $S$ are
colored, and we say that a (not necessarily convex) spanned
polygon is monochromatic if all its vertices have the same
color. Moreover, a polygon is called empty if it does not
contain any points of $S$ in its interior. We show that any
bichromatic set of $n \geq 5044$ points in $\mathcal{R}^2$
in general position determines at least one empty,
monochromatic quadrilateral (and thus linearly many).},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{ahhhv-lbpsa-09,
author = {O.~Aichholzer and T.~Hackl and C.~Huemer and F.~Hurtado
and B.~Vogtenhuber},
title = {{{Large bichromatic point sets admit empty monochromatic $4$-gons}}},
booktitle = {Proc. $25^{th}$ European Workshop on Computational
Geometry EuroCG '09},
category = {3b},
pages = {133--136},
pdf = {/files/publications/geometry/ahhhv-lbpsa-09.pdf},
oaich_label = {78},
thackl_label = {17C},
year = 2009,
address = {Brussels, Belgium},
abstract = {We consider a variation of a problem stated by Erd\"os and
Szekeres in 1935 about the existence of a number
$f^\textrm{ES}(k)$ such that any set $S$ of at least
$f^\textrm{ES}(k)$ points in general position in the plane
has a subset of $k$ points that are the vertices of a
convex $k$-gon. In our setting the points of $S$ are
colored, and we say that a (not necessarily convex) spanned
polygon is monochromatic if all its vertices have the same
color. Moreover, a polygon is called empty if it does not
contain any points of $S$ in its interior. We show that any
bichromatic set of $n \geq 5044$ points in $\mathcal{R}^2$
in general position determines at least one empty,
monochromatic quadrilateral (and thus linearly many).},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{affhhuv-mimp-09,
author = {O. Aichholzer and R.~Fabila-Monroy and
D.~Flores-Pe{\~n}aloza and T.~Hackl and C.~Huemer and
J.~Urrutia and B.~Vogtenhuber},
title = {{{Modem Illumination of Monotone Polygons}}},
booktitle = {Proc. $25^{th}$ European Workshop on Computational
Geometry EuroCG '09},
category = {3b},
pages = {167--170},
arxiv = {1503.05062},
pdf = {/files/publications/geometry/affhhuv-mimp-09.pdf},
oaich_label = {80},
thackl_label = {16C},
year = 2009,
address = {Brussels, Belgium},
abstract = {We study a generalization of the classical problem of
illumination of polygons. Instead of modeling a light
source we model a wireless device whose radio signal can
penetrate a given number $k$ of walls. We call these
objects $k$-modems and study the minimum number of
$k$-modems necessary to illuminate monotone and monotone
orthogonal polygons. We show that every monotone polygon on
$n$ vertices can be illuminated with $\left\lceil
\frac{n}{2k} \right\rceil$ $k$-modems and exhibit examples
of monotone polygons requiring $\left\lceil \frac{n}{2k+2}
\right\rceil$ $k$-modems. For monotone orthogonal polygons,
we show that every such polygon on $n$ vertices can be
illuminated with $\left\lceil \frac{n}{2k+4} \right\rceil$
$k$-modems and give examples which require $\left\lceil
\frac{n}{2k+4} \right\rceil$ $k$-modems for $k$ even and
$\left\lceil \frac{n}{2k+6} \right\rceil$ for $k$ odd.},
originalfile = {/geometry/cggg.bib}
}
@article{ahhhssv-mmaps-09,
author = {O. Aichholzer and T. Hackl and M.~Hoffmann and C.~Huemer
and A.~P{\'o}r and F.~Santos and B.~Speckmann and B.~Vogtenhuber},
title = {{{Maximizing Maximal Angles for Plane Straight Line Graphs}}},
year = 2013,
volume = {46},
number = {1},
journal = {Computational Geometry: Theory and Applications},
pages = {17--28},
category = {3a},
oaich_label = {65c},
thackl_label = {9J},
pdf = {/files/publications/geometry/ahhhpssv-mmaps-12.pdf},
doi = {http://dx.doi.org/10.1016/j.comgeo.2012.03.002},
eprint = {0705.3820},
archiveprefix = {arXiv},
abstract = {Let $G=(S, E)$ be a plane straight line graph on a finite
point set $S\subset {R}^2$ in general position. For a point
$p\in S$ let the {\em maximum incident angle} of $p$ in $G$
be the maximum angle between any two edges of $G$ that
appear consecutively in the circular order of the edges
incident to $p$. A plane straight line graph is called {\em
$\varphi$-open} if each vertex has an incident angle of
size at least $\varphi$. In this paper we study the
following type of question: What is the maximum angle
$\varphi$ such that for any finite set $S\subset {R}^2$ of
points in general position we can find a graph from a
certain class of graphs on $S$ that is $\varphi$-open? In
particular, we consider the classes of triangulations,
spanning trees, and paths on $S$ and give tight bounds in
all but one cases.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{ahhhssv-mmaps-07b,
author = {O. Aichholzer and T. Hackl and M.~Hoffmann and C.~Huemer
and A.~Por and F.~Santos and B.~Speckmann and
B.~Vogtenhuber},
title = {{{Maximizing Maximal Angles for Plane Straight Line Graphs}}},
pdf = {/files/publications/geometry/ahhhssv-mmaps-07b.pdf},
oaich_label = {65b},
thackl_label = {9C},
booktitle = {Lecture Notes in Computer Science (LNCS), Proc. $10^{th}$
International Workshop on Algorithms and Data Structures
(WADS)},
volume = {4619},
address = {Halifax, Nova Scotia, Canada},
pages = {458--469},
year = 2007,
eprint = {0705.3820},
doi = {10.1007/978-3-540-73951-7_40},
abstract = {Let $G=(S, E)$ be a plane straight line graph on a finite
point set $S\subset {R}^2$ in general position. For a point
$p\in S$ let the {\em maximum incident angle} of $p$ in $G$
be the maximum angle between any two edges of $G$ that
appear consecutively in the circular order of the edges
incident to $p$. A plane straight line graph is called {\em
$\varphi$-open} if each vertex has an incident angle of
size at least $\varphi$. In this paper we study the
following type of question: What is the maximum angle
$\varphi$ such that for any finite set $S\subset {R}^2$ of
points in general position we can find a graph from a
certain class of graphs on $S$ that is $\varphi$-open? In
particular, we consider the classes of triangulations,
spanning trees, and paths on $S$ and give tight bounds in
all but one cases.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{ahhhssv-mmaps-07,
author = {O. Aichholzer and T.~Hackl and M.~Hoffmann and C.~Huemer
and F.~Santos and B.~Speckmann and B.~Vogtenhuber},
title = {{{Maximizing Maximal Angles for Plane Straight Line Graphs}}},
booktitle = {Proc. $23^{rd}$ European Workshop on Computational
Geometry EuroCG '07},
pages = {98--101},
pdf = {/files/publications/geometry/ahhhssv-mmaps-07.pdf},
oaich_label = {65},
thackl_label = {9C},
year = 2007,
address = {Graz, Austria},
eprint = {0705.3820},
archiveprefix = {arXiv},
htmlnote = {Also available as FSP-report S092-48, Austria, 2007, at http://www.industrial-geometry.at/techrep.php.},
abstract = {Let $G=(S, E)$ be a plane straight line graph on a finite
point set $S\subset {R}^2$ in general position. For a point
$p\in S$ let the {\em maximum incident angle} of $p$ in $G$
be the maximum angle between any two edges of $G$ that
appear consecutively in the circular order of the edges
incident to $p$. A plane straight line graph is called {\em
$\varphi$-open} if each vertex has an incident angle of
size at least $\varphi$. In this paper we study the
following type of question: What is the maximum angle
$\varphi$ such that for any finite set $S\subset {R}^2$ of
points in general position we can find a graph from a
certain class of graphs on $S$ that is $\varphi$-open? In
particular, we consider the classes of triangulations,
spanning trees, and paths on $S$ and give tight bounds in
all but one cases.},
originalfile = {/geometry/cggg.bib}
}
@article{ahhhkv-npg-06a,
author = {O. Aichholzer and T. Hackl and C.~Huemer and F.~Hurtado
and H.~Krasser and B.~Vogtenhuber},
title = {{{On the number of plane geometric graphs}}},
journal = {Graphs and Combinatorics (Springer)},
pages = {67--84},
volume = {23(1)},
oaich_label = {58a},
thackl_label = {3J},
category = {3a},
postscript = {/files/publications/geometry/ahhhkv-npgg-06.ps.gz},
year = 2007,
doi = {https://doi.org/10.1007/s00373-007-0704-5},
abstract = {We investigate the number of plane geometric, i.e.,
straight-line, graphs, a set $S$ of $n$ points in the plane
admits. We show that the number of plane geometric graphs
and connected plane geometric graphs as well as the number
of cycle-free plane geometric graphs is minimized when $S$
is in convex position. Moreover, these results hold for all
these graphs with an arbitrary but fixed number of edges.
Consequently, we provide a unified proof that the
cardinality of any family of acyclic graphs (for example
spanning trees, forests, perfect matchings, spanning paths,
and more) is minimized for point sets in convex position.
In addition we construct a new extremal configuration, the
so-called double zig-zag chain. Most noteworthy this
example bears $\Theta^*(\sqrt{72}\,^n)$ =
$\Theta^*(8.4853^n)$ triangulations and
$\Theta^*(41.1889^n)$ plane graphs (omitting polynomial
factors in both cases), improving the previously known best
maximizing examples.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{ahhhkv-npg-06,
author = {O. Aichholzer and T. Hackl and C.~Huemer and F.~Hurtado
and H.~Krasser and B.~Vogtenhuber},
title = {{{On the number of plane graphs}}},
booktitle = {Proc. $17^{th}$ Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA)},
pages = {504-513},
year = 2006,
address = {Miami, Florida, USA},
category = {3b},
oaich_label = {58},
thackl_label = {3C},
pdf = {/files/publications/geometry/ahhhkv-npg-06.pdf},
htmlnote = {Also available as FSP-report S092-8, Austria, 2006, at http://www.industrial-geometry.at/techrep.php.},
abstract = {We investigate the number of plane geometric, i.e.,
straight-line, graphs, a set $S$ of $n$ points in the plane
admits. We show that the number of plane graphs and
connected plane graphs as well as the number of cycle-free
plane graphs is minimized when $S$ is in convex position.
Moreover, these results hold for all these graphs with an
arbitrary but fixed number of edges. Consequently, we
provide simple proofs that the number of spanning trees,
cycle-free graphs (forests), perfect matchings, and
spanning paths is also minimized for point sets in convex
position. In addition we construct a new extremal
configuration, the so-called double zig-zag chain. Most
noteworthy this example bears $\Theta^*(\sqrt{72}\,^n)$ =
$\Theta^*(8.4853^n)$ triangulations and
$\Theta^*(41.1889^n)$ plane graphs (omitting polynomial
factors in both cases), improving the previously known best
maximizing examples.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{ahhhkv-bnpg-06,
author = {O. Aichholzer and T. Hackl and C.~Huemer and F.~Hurtado
and H.~Krasser and B.~Vogtenhuber},
title = {{{Bounding the number of plane graphs}}},
booktitle = {Proc. $15^{th}$ Annual Fall Workshop on Computational
Geometry and Visualization},
pages = {31-32},
year = 2005,
address = {Philadelphia, Pennsylvania, USA},
category = {3b},
oaich_label = {58b},
thackl_label = {3C},
abstract = {We investigate the number of plane geometric, i.e.,
straight-line, graphs, a set $S$ of $n$ points in the plane
admits. We show that the number of plane graphs and
connected plane graphs as well as the number of cycle-free
plane graphs is minimized when $S$ is in convex position.
Moreover, these results hold for all these graphs with an
arbitrary but fixed number of edges. Consequently, we
provide simple proofs that the number of spanning trees,
cycle-free graphs (forests), perfect matchings, and
spanning paths is also minimized for point sets in convex
position. In addition we construct a new extremal
configuration, the so-called double zig-zag chain. Most
noteworthy this example bears $\Theta^*(\sqrt{72}\,^n)$ =
$\Theta^*(8.4853^n)$ triangulations and
$\Theta^*(41.1889^n)$ plane graphs (omitting polynomial
factors in both cases), improving the previously known best
maximizing examples.},
originalfile = {/geometry/cggg.bib}
}
@article{aaghhhkrv-mefpp-06,
author = {O. Aichholzer and F. Aurenhammer and P. Gonzalez-Nava and
T.~Hackl and C.~Huemer and F.~Hurtado and H.~Krasser and
S.~Ray and B.~Vogtenhuber},
title = {{{Matching Edges and Faces in Polygonal Partitions}}},
journal = {Computational Geometry: Theory and Applications},
pages = {134--141},
volume = {39(2)},
category = {3a},
oaich_label = {57a},
thackl_label = {2J},
year = 2008,
postscript = {/files/publications/geometry/aaghhhkrv-mefpp-06.ps.gz},
abstract = {We define general Laman (count) conditions for edges and
faces of polygonal partitions in the plane. Several
well-known classes, including $k$-regular partitions,
$k$-angulations, and rank $k$ pseudo-triangulations, are
shown to fulfill such conditions. As a consequence
non-trivial perfect matchings exist between the edge sets
(or face sets) of two such structures when they live on the
same point set. We also describe a link to spanning tree
decompositions that applies to quadrangulations and certain
pseudo-triangulations.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{aaghhhkrv-mefpp-05,
author = {O. Aichholzer and F. Aurenhammer and P.~Gonzalez-Nava and
T.~Hackl and C.~Huemer and F.~Hurtado and H.~Krasser and
S.~Ray and B.~Vogtenhuber},
title = {{{Matching Edges and Faces in Polygonal Partitions}}},
booktitle = {Proc. $17^{th}$ Annual Canadian Conference on
Computational Geometry CCCG 2005},
pages = {123--126},
year = 2005,
address = {Windsor, Ontario, Canada},
category = {3b},
oaich_label = {57},
thackl_label = {2C},
postscript = {/files/publications/geometry/aaghhhkrv-mefpp-05.ps.gz},
htmlnote = {Also available as FSP-report S092-4, Austria, 2005, at http://www.industrial-geometry.at/techrep.php.},
abstract = {We define general Laman (count) conditions for edges and
faces of polygonal partitions in the plane. Several
well-known classes, including $k$-regular partitions,
$k$-angulations, and rank $k$ pseudo-triangulations, are
shown to fulfill such conditions. As a consequence
non-trivial perfect matchings exist between the edge sets
(or face sets) of two such structures when they live on the
same point set. We also describe a link to spanning tree
decompositions that applies to quadrangulations and certain
pseudo-triangulations.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{akpv-got-12,
author = {Oswin Aichholzer and Matias Korman and Alexander Pilz and Birgit Vogtenhuber},
title = {{{Geodesic Order Types}}},
rembooktitle = {Computing nd Combinatorics, Proc. 18$^{th}$ Annual International Computing and Combinatorics Conference},
booktitle = {{Proc. $18^{th}$ International Computing and Combinatorics Conference (COCOON 2012)}},
pages = {216--227},
year = {2012},
address = {Sydney, Australia},
month = {August},
editor = {Joachim Gudmundsson and Juli{\'a}n Mestre and Taso Viglas},
series = {Lecture Notes in Computer Science},
volume = {7434},
publisher = {Springer},
eprint = {1708.06064},
archiveprefix = {arXiv},
doi = {10.1007/978-3-642-32241-9_19},
abstract = {The geodesic between two points $a$ and $b$ in the interior of a simple polygon~$P$ is the shortest polygonal path inside $P$ that connects $a$ to $b$.
It is thus the natural generalization of straight line segments on unconstrained point sets to polygonal environments.
In this paper we use this extension to generalize the concept of the order type of a set of points in the Euclidean plane to geodesic order types.
In particular, we show that, for any set $S$ of points and an ordered subset $\blue \subseteq S$ of at least four points, one can always construct a polygon $P$ such that the points of $\blue$ define the geodesic hull of~$S$ w.r.t.~$P$, in the specified order.
Moreover, we show that an abstract order type derived from the dual of the Pappus arrangement can be realized as a geodesic order type.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{klmpv-mddt-14,
author = {Matias Korman and Stefan Langerman and Wolfgang Mulzer and Alexander Pilz and Maria Saumell and Birgit Vogtenhuber},
title = {{{Minimum Dual Diameter Triangulations}}},
booktitle = {Proc. $30^{th}$ European Workshop on Computational Geometry (EuroCG 2014)},
year = {2014},
month = {March},
pages = {online},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{abhpv-ltdbm-14,
author = {Aichholzer, Oswin and Barba, Luis and Hackl, Thomas
and Pilz, Alexander and Vogtenhuber, Birgit},
title = {{{Linear Transformation Distance for Bichromatic
Matchings}}},
booktitle = {Proc. 30\textsuperscript{th} Symposium on
Computational Geometry (SOCG 2014)},
remseries = {SOCG'14},
year = {2014},
isbn = {978-1-4503-2594-3},
location = {Kyoto, Japan},
pages = {154--162},
articleno = {154},
numpages = {9},
url = {http://doi.acm.org/10.1145/2582112.2582151},
doi = {http://dx.doi.org/10.1145/2582112.2582151},
acmid = {2582151},
publisher = {ACM},
remaddress = {New York, NY, USA},
keywords = {bichromatic point set, compatible matchings,
perfect matchings, reconfiguration problem,
transformation graph},
arxiv = {1312.0884v1},
pdf = {/files/publications/geometry/abhpv-ltdbm-14.pdf},
category = {3b},
thackl_label = {41C},
abstract = {Let $P=B\cup R$ be a set of $2n$ points in general
position, where $B$ is a set of $n$ blue points and
$R$ a set of $n$ red points. A \emph{$BR$-matching}
is a plane geometric perfect matching on $P$ such
that each edge has one red endpoint and one blue
endpoint. Two $BR$-matchings are compatible if their
union is also plane.\\ The \emph{transformation
graph of $BR$-matchings} contains one node for each
$BR$-matching and an edge joining two such nodes if
and only if the corresponding two $BR$-matchings are
compatible. In SoCG 2013 it has been shown by
Aloupis, Barba, Langerman, and Souvaine that this
transformation graph is always connected, but its
diameter remained an open question. In this paper we
provide an alternative proof for the connectivity of
the transformation graph and prove an upper bound of
$2n$ for its diameter, which is asymptotically
tight.},
originalfile = {/geometry/cggg.bib}
}
@mastersthesis{v-opg-07,
author = {B. Vogtenhuber},
title = {{{On Plane Straight-Line Graphs}}},
school = {IST-TU Graz, Austria},
year = {2007},
month = {January},
category = {11},
note = {Supervisor: Oswin Aichholzer},
pdf = {/files/publications/geometry/v-opg-07.pdf},
abstract = {Geometric Graph Theory is a branch of both, Computational
Geometry and Graph Theory, which deals with properties of
straight-line embeddings of graphs as well as algorithmic
issues. In this diploma thesis, we consider three topics
within the area of plane geometric graphs, namely
angle-constrained graphs, graph enumeration with Gray
codes, and counting of graphs. The obtained results include
(1)~tight angle bounds for the openness of certain classes
of angle-constrained graphs, thereby generalizing the
concept of pointed pseudo-triangulations; (2)~Gray codes
for enumerating plane spanning trees, connected plane
graphs, and all plane graphs in an efficient way; (3)~lower
and upper bounds for the asymptotically minimal and maximal
numbers of certain types of geometric graphs. Results
obtained during the work of this thesis have already been
presented at international conferences and will appear as
refereed journal articles.},
originalfile = {/geometry/cggg.bib}
}
@article{arsv-pdpg-11,
author = {O. Aichholzer and G. Rote and A. Schulz and B.
Vogtenhuber},
title = {{{Pointed Drawings of Planar Graphs}}},
year = 2012,
journal = {Computational Geometry: Theory and Applications},
pages = {482--494},
note = {special issue of CCCG 2007},
category = {3a},
doi = {10.1016/j.comgeo.2010.08.001},
pdf = {/files/publications/geometry/arsv-pdpg-11.pdf},
abstract = {We study the problem how to draw a planar graph such that
every vertex is incident to an angle greater than $\pi$. In
general a straight-line embedding cannot guarantee this
property. We present algorithms which construct such
drawings with either tangent-continuous biarcs or quadratic
B\'ezier curves (parabolic arcs), even if the
\mbox{positions} of the vertices are predefined by a given
plane straight-line embedding of the graph. Moreover, the
graph can be embedded with circular arcs if the vertices
can be placed arbitrarily. The topic is related to
non-crossing drawings of multigraphs and vertex labeling.},
originalfile = {/geometry/cggg.bib}
}
@phdthesis{v-cacpp-11,
author = {B. Vogtenhuber},
title = {{{Combinatorial Aspects of [Colored] Point Sets in the
Plane}}},
school = {Institute for Software Technology, Graz University of
Technology, Graz, Austria},
year = {2011},
month = {December},
note = {Supervisor: Oswin Aichholzer},
pdf = {/files/publications/geometry/v-cacpp-11.pdf},
abstract = {Combinatorial geometry and graph theory are both areas in
the field of discrete mathematics. The study of
combinatorial aspects of point sets in the plane and graphs
based on them is situated in the intersection of these
areas and also includes aspects of computational geometry
and graph drawing.
We study variations of the classical Erd{\H{o}}s-Szekeres
problems on convex $k$-gons and $k$-holes. Relaxing the
convexity condition, we show structural results and bounds
on the numbers of $k$-gons and $k$-holes. Most noteworthy,
for constant $k$ and sufficiently large $n$, we give a
quadratic lower bound for the number of \mbox{$k$-holes}
and show that this number is maximized by sets in convex
position. For bichromatic point sets, we show that every
sufficiently large such set contains a monochromatic 4-hole.
Continuing with investigations on bichromatic point sets, a
famous problem is Zarankiewicz's conjecture on the crossing
number of the complete bipartite graph. Studying
rectilinear versions of this conjecture, we present several
interesting observations. The main question remains
unsettled even for these variations though. We also
consider the existence of different kinds of compatible
colored matchings for given bichromatic graphs of certain
classes and present bounds on their cardinalities.
The study of Delaunay triangulations is a central topic in
geometric graph theory. We investigate the question of
finding a set of additional points $W$ for a given set $B$
with $n$ points such that the Delaunay triangulation of the
joint set $B\dunion W$ does not contain any edge spanned by
two points of $B$. Improving the previously best known
bounds, we show that $|W|\leq3n/2$ points are sufficient in
general and $|W|\leq5n/4$ points suffice if $B$ is a convex
set. We also present a lower bound of $|W|\geq n-1$.
Investigating pointed pseudo-triangulations, we study the
existence of compatible pointed pseudo-triangulations whose
union is a maximal plane graph. We present a construction
for pairs of such pseudo-triangulations for a given point
set. A given pointed pseudo-triangulation in general does
not admit such a compatible pseudo-triangulation. Finally,
we generalize the pointedness property of pointed
pseudo\hyp{}triangulations to other types of graphs. We
consider (1) redrawing the edges of a given plane
straight-line graph such that all vertices become pointed;
and (2) embedding a planar graph such that every vertex has
all its incident edges within a small angle. We show that
both tasks can be realized using B\'ezier-curves, biarcs or
polygonal chains of length two as edges.},
fadress = {},
fkey = {},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{auv-b6bps-13,
author = {O.~Aichholzer and J.~Urrutia and B.~Vogtenhuber},
title = {{{Balanced 6-holes in bichromatic point sets}}},
booktitle = {Proc. of the $16^{th}$ Japan Conference on Discrete and
Computational Geometry and Graphs (JCDCG$^2$ 2013)},
year = 2013,
address = {Tokyo, Japan},
category = {3b},
pdf = {/files/publications/geometry/auv-b6bps-13.pdf},
abstract = {We consider an Erd{\H{o}}s type question on $k$-holes (empty
$k$-gons) in bichromatic point sets. For a bichromatic
point set $S = R \cup B$, a balanced $2k$-hole in $S$ is
spanned by $k$ points of $R$ and $k$ points of $B$. We show
that if $|R| = |B| = n$, then the number of balanced
6-holes in $S$ is at least $1/45n^2-\Theta(n)$.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{arsv-pdpg-07,
author = {O. Aichholzer and G. Rote and A. Schulz and B.
Vogtenhuber},
title = {{{Pointed Drawings of Planar Graphs}}},
booktitle = {Proc. $19th$ Annual Canadian Conference on Computational
Geometry CCCG 2007},
pages = {237--240},
year = 2007,
address = {Ottawa, Ontario, Canada},
category = {3b},
oaich_label = {72},
pdf = {/files/publications/geometry/arsv-pdpg-07.pdf},
abstract = {We study the problem how to draw a planar graph such that
every vertex is incident to an angle greater than $\pi$. In
general a straight-line embedding cannot guarantee this
property. We present algorithms which construct such
drawings with either tangent-continuous biarcs or quadratic
B\'ezier curves (parabolic arcs), even if the
\mbox{positions} of the vertices are predefined by a given
plane straight-line embedding of the graph. Moreover, the
graph can be embedded with circular arcs if the vertices
can be placed arbitrarily. The topic is related to
non-crossing drawings of multigraphs and vertex labeling.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{ahv-cmbps-12,
author = {O.~Aichholzer and F.~Hurtado and B.~Vogtenhuber},
title = {{{Compatible Matchings for Bichromatic Plane Straight-line
Graphs}}},
booktitle = {Proc. $28^{th}$ European Workshop on Computational
Geometry EuroCG '12},
pages = {257--260},
year = 2012,
address = {Assisi, Italy},
category = {3b},
pdf = {/files/publications/geometry/ahv-cmbps-12.pdf},
abstract = {Two plane graphs with the same vertex set are compatible
if their union is again a plane graph. We consider
bichromatic plane straight-line graphs with vertex set $S$
consisting of the same number of red and blue points, and
(perfect) matchings which are compatible to them. For
several different classes $\mathcal{C}$ of graphs, we
present lower and upper bounds such that any given graph
$G(S) \in \mathcal{C}$ admits a compatible (perfect)
matching with this many disjoint edges.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{aahv-gceps-06,
author = {O. Aichholzer and F. Aurenhammer and C. Huemer and B.
Vogtenhuber},
title = {{{Gray code enumeration of plane straight-line graphs}}},
booktitle = {Proc. $22^{nd}$ European Workshop on Computational
Geometry EuroCG '06},
pages = {71--74},
category = {3b},
oaich_label = {62},
year = 2006,
address = {Delphi, Greece},
postscript = {/files/publications/geometry/aahv-gceps-06.ps.gz},
htmlnote = {Also available as FSP-report S092-7, Austria, 2006, at http://www.industrial-geometry.at/techrep.php.},
abstract = {We develop Gray code enumeration schemes for geometric
straight-line graphs in the plane. The considered graph
classes include plane graphs, connected plane graphs, and
plane spanning trees. Previous results were restricted to
the case where the underlying vertex set is in convex
position.},
originalfile = {/geometry/cggg.bib}
}
@article{auv-b6lsb-13,
author = {Oswin Aichholzer and Jorge Urrutia and Birgit
Vogtenhuber},
title = {{{Balanced 6-holes in linearly separable bichromatic point
sets}}},
journal = {Electronic Notes in Discrete Mathematics},
volume = {44},
pages = {181 - 186},
year = 2013,
category = {3b},
note = {Special issue dedicated to LAGOS2013},
doi = {http://dx.doi.org/10.1016/j.endm.2013.10.028},
url = {http://www.sciencedirect.com/science/article/pii/S1571065313002448},
doi = {http://dx.doi.org/10.1016/j.endm.2013.10.028},
abstract = {We consider an Erd{\H{o}}s type question on $k$-holes (empty
$k$-gons) in bichromatic point sets. For a bichromatic
point set $S = R \cup B$, a balanced $2k$-hole in $S$ is
spanned by $k$ points of $R$ and $k$ points of $B$. We show
that if $R$ and $B$ are linearly separable and $|R| = |B| =
n$, then the number of balanced 6-holes in $S$ is at least
$1/15n^2-\Theta(n)$.},
originalfile = {/geometry/cggg.bib}
}
@article{aahv-gceps-07,
author = {O. Aichholzer and F. Aurenhammer and C. Huemer and B.
Vogtenhuber},
title = {{{Gray code enumeration of plane straight-line graphs}}},
journal = {Graphs and Combinatorics (Springer)},
pages = {467--479},
volume = {23(5)},
category = {3a},
oaich_label = {62b},
year = 2007,
doi = {10.1007/s00373-007-0750-z},
postscript = {/files/publications/geometry/aahv-gceps-07.pdf},
abstract = {We develop Gray code enumeration schemes for geometric
straight-line graphs in the plane. The considered graph
classes include plane graphs, connected plane graphs, and
plane spanning trees. Previous results were restricted to
the case where the underlying vertex set is in convex
position.},
originalfile = {/geometry/cggg.bib}
}
@article{akpv-got-14,
author = {Oswin Aichholzer and Matias Korman and Alexander Pilz and Birgit Vogtenhuber},
title = {{{Geodesic Order Types}}},
journal = {Algorithmica},
volume = {70},
number = {1},
year = {2014},
pages = {112--128},
doi = {http://dx.doi.org/10.1007/s00453-013-9818-8},
eprint = {1708.06064},
archiveprefix = {arXiv},
archiveprefix = {arXiv},
url = {http://link.springer.com/article/10.1007\%2Fs00453-013-9818-8},
pdf = {/files/publications/geometry/akpv-got-14.pdf},
abstract = {The geodesic between two points a and b in the interior of a simple polygon P is the shortest polygonal path inside P that connects a to b. It is thus the natural generalization of straight line segments on unconstrained point sets to polygonal environments. In this paper we use this extension to generalize the concept of the order type of a set of points in the Euclidean plane to geodesic order types. In particular, we show that, for any set S of points and an ordered subset B ⊆ S of at least four points, one can always construct a polygon P such that the points of B define the geodesic hull of S w.r.t. P, in the specified order. Moreover, we show that an abstract order type derived from the dual of the Pappus arrangement can be realized as a geodesic order type.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{aafrv-nsdfc-14,
author = {Bernardo M.~\'{A}brego and Oswin Aichholzer and Silvia Fern\'{a}ndez-Merchant and Pedro Ramos and Birgit
Vogtenhuber},
title = {{{Non-Shellable Drawings of $K_n$ with Few Crossings}}},
booktitle = {Proc. $26^{th}$ Annual Canadian Conference on
Computational Geometry CCCG 2014},
pages = {online},
year = 2014,
address = {Halifax, Nova Scotia, Canada},
category = {3b},
abstract = {In the early 60s, Harary and Hill conjectured
$H(n):=\frac{1}{4}\lfloor\frac{n}{2}\rfloor\lfloor\frac{n-1}{2}\rfloor\lfloor\frac{n-2}{2}\rfloor\lfloor\frac{n-3}{2}\rfloor$
to be the minimum number of crossings among all drawings of the complete graph $K_n$.
It has recently been shown that this conjecture holds for so-called
shellable drawings of $ K_n $. For $ n \geq 11 $ odd, we construct a non-shellable family of
drawings of $ K_n $ with exactly $H(n)$ crossings. In particular,
every edge in our drawings is intersected by at least one other
edge. So far only two other families were known to achieve the
conjectured minimum of crossings, both of them being shellable.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{ahhv-ssmvd-14,
author = {Oswin Aichholzer and Thomas Hackl and Stefan Huber and Birgit Vogtenhuber},
title = {{{Straight Skeletons by Means of Voronoi Diagrams Under Polyhedral Distance Functions}}},
booktitle = {Proc. $26^{th}$ Annual Canadian Conference on
Computational Geometry (CCCG 2014)},
pages = {online},
year = 2014,
address = {Halifax, Nova Scotia, Canada},
category = {3b},
arxiv = {},
pdf = {/files/publications/geometry/ahhv-ssmvd-14.pdf},
thackl_label = {42C},
abstract = {We consider the question under which circumstances the straight
skeleton and the Voronoi diagram of a given input shape coincide.
More precisely, we investigate convex distance functions that stem
from centrally symmetric convex polyhedra as unit balls and derive
sufficient and necessary conditions for input shapes in order to
obtain identical straight skeletons and Voronoi diagrams with
respect to this distance function.
This allows us to present a new approach for generalizing straight
skeletons by means of Voronoi diagrams, so that the straight
skeleton changes continuously when vertices of the input shape are
dislocated, that is, no discontinuous changes as in the Euclidean
straight skeleton occur.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{afhpruv-otcsl-14,
author = {Oswin Aichholzer and Ruy Fabila-Monroy and Ferran Hurtado
and Pablo Perez-Lantero and Andres J. Ruiz-Vargas and Jorge Urrutia and Birgit Vogtenhuber},
title = {{{Order types and cross-sections of line arrangements in $R^3$}}},
booktitle = {Proc. $26^{th}$ Annual Canadian Conference on
Computational Geometry CCCG 2014},
pages = {online},
year = 2014,
address = {Halifax, Nova Scotia, Canada},
category = {3b},
abstract = {We consider sets of $n$ labeled lines in general position in ${{\sf l} \kern -.10em {\sf R} }^3$, and
study the order types of point sets that stem from the intersections
of the lines with (directed) planes, not parallel to any given line.
As a main result we show that the number of different order
types that can be obtained as cross-sections of these lines is
$O(n^9)$, and that this bound is tight.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{ahlmv-efdpc-14,
author = {Oswin Aichholzer and Thomas Hackl and Sarah Lutteropp and Tamara Mchedlidze and Birgit Vogtenhuber},
title = {{{Embedding Four-directional Paths on Convex Point Sets}}},
booktitle = {Proc. $22^{nd}$ International Symposium on Graph Drawing (GD 2014)},
series = {Lecture Notes in Computer Science (LNCS)},
volume = {8871},
nopublisher = {Springer, Heidelberg},
editor = {C.~Duncan and A.~Symvonis},
pages = {355--366},
year = 2014,
address = {W{\"u}rzburg, Germany},
category = {3b},
arxiv = {1408.4933},
pdf = {/files/publications/geometry/ahlmv-efdpc-14.pdf},
thackl_label = {44C},
abstract = {A directed path whose edges are assigned labels ``up'', ``down'', ``right'', or ``left'' is called \emph{four-directional}, and \emph{three-directional} if at most three out of the four labels are used.
A \emph{direction-consistent embedding} of an \mbox{$n$-vertex} four-directional path $P$ on a set $S$ of $n$ points in the plane
is a straight-line drawing of $P$ where each vertex of $P$ is mapped to a distinct point of $S$ and every edge points to the direction specified by its label.
We study planar direction-consistent embeddings of three- and four-directional paths and provide a complete picture of the problem for convex point sets.},
originalfile = {/geometry/cggg.bib}
}
@article{ahlmv-efdpc-15,
author = {Oswin Aichholzer and Thomas Hackl and Sarah Lutteropp and Tamara Mchedlidze and Birgit Vogtenhuber},
title = {{{Embedding Four-directional Paths on Convex Point Sets}}},
journal = {Journal of Graph Algorithms and Applications},
year = 2015,
volume = {19},
number = {2},
pages = {743--759},
thackl_label = {44J},
category = {3a},
issn = {1526-1719},
doi = {http://dx.doi.org/10.7155/jgaa.00368},
arxiv = {1408.4933},
pdf = {/files/publications/geometry/ahlmv-efdpc-14.pdf},
abstract = {A directed path whose edges are assigned labels
``up'', ``down'', ``right'', or ``left'' is called
\emph{four-directional}, and
\emph{three-directional} if at most three out of the
four labels are used. A \emph{direction-consistent
embedding} of an \mbox{$n$-vertex} four-directional
path $P$ on a set $S$ of $n$ points in the plane is
a straight-line drawing of $P$ where each vertex of
$P$ is mapped to a distinct point of $S$ and every
edge points to the direction specified by its label.
We study planar direction-consistent embeddings of
three- and four-directional paths and provide a
complete picture of the problem for convex point
sets.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{ahpsv-dmgdc-15,
author = {Oswin Aichholzer and Thomas Hackl and Alexander Pilz and Gelasio Salazar and Birgit Vogtenhuber},
title = {{{Deciding monotonicity of good drawings of the complete graph}}},
booktitle = {Proc. XVI Spanish Meeting on Computational Geometry (EGC 2015)},
pages = {33--36},
year = {2015},
category = {3b},
thackl_label = {47C},
pdf = {/files/publications/geometry/ahpsv-dmgdc-15.pdf},
abstract = {We describe an $O(n^5)$ time algorithm for deciding whether a good drawing of the complete graph $K_n$, given in terms of its rotation system, can be re-drawn using only $x$-monotone arcs.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{abhprvv-hitcps-16,
author = {O.~Aichholzer and M.~Balko and T.~Hackl and A.~Pilz and P.~Ramos and B.~Vogtenhuber and P.~Valtr},
title = {{{Holes in two convex point sets}}},
booktitle = {Proc. $32^{st}$ European Workshop on Computational Geometry EuroCG '16},
pages = {263--266},
year = 2016,
address = {Lugano, Switzerland},
category = {3b},
eprint = {},
pdf = {/files/publications/geometry/abhprvv-hitcps-16.pdf},
thackl_label = {52C},
abstract = {Let $S$ be a finite set of $n$ points in the plane in
general position. A $k-hole$ of $S$ is a simple
polygon with $k$ vertices from $S$ and no points of
$S$ in its interior. A simple polygon $P$ is
$l$-convex if no straight line intersects the
interior of $P$ in more than $l$ connected
components. Moreover, a point set $S$ is $l$-convex
if there exists an $l$-convex polygonalization of
$S$. Considering a typical Erd{\H{o}}s-Szekeres type
problem we show that every 2-convex point set of
size $n$ contains a convex hole of size $\Omega(log n)$.
This is in contrast to the well known fact that
there exist general point sets of arbitrary size
that do not contain a convex 7-hole. Further, we
show that our bound is tight by providing a
construction for 2-convex point sets with holes of
size at most $O(log n)$.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{abhprvv-hi2cps-17,
author = {O.~Aichholzer and M.~Balko and T.~Hackl and A.~Pilz and P.~Ramos and P.~Valtr and B.~Vogtenhuber},
title = {{{Holes in 2-convex point sets}}},
booktitle = {Proc. $28^{th}$ International Workshop on Combinatorial Algorithms (IWOCA2017)},
series = {Lecture Notes in Computer Science (LNCS)},
volume = {10765},
pages = {169--181},
year = 2018,
address = {Newcastle, Australia},
doi = {https://doi.org/10.1007/978-3-319-78825-8_14},
abstract = {Let $S$ be a set of $n$ points in the plane in general position
(no three points from $S$ are collinear).
For a positive integer $k$, a \emph{$k$-hole} in $S$ is a convex polygon
with $k$ vertices from~$S$ and no points of~$S$ in its interior.
For a positive integer $l$, a simple polygon~$P$ is \emph{$l$-convex}
if no straight line intersects the interior of~$P$ in more than $l$ connected components.
A point set $S$ is \emph{$l$-convex} if there exists an $l$-convex polygonization of $S$.
Considering a typical Erd{\H{o}}s--Szekeres-type problem, we show that every 2-convex point
set of size~$n$ contains an $\Omega(\log n)$-hole.
In comparison, it is well known that there exist arbitrarily
large point sets in general position with no 7-hole.
Further, we show that our bound is tight by constructing 2-convex point sets with holes
of size at most $O(\log n)$.},
originalfile = {/geometry/cggg.bib}
}
@article{abhprvv-hi2cps-18,
author = {O.~Aichholzer and M.~Balko and T.~Hackl and A.~Pilz and P.~Ramos and P.~Valtr and B.~Vogtenhuber},
title = {{{Holes in 2-convex point sets}}},
journal = {Computational Geometry: Theory and Applications},
volume = {74},
pages = {38--49},
year = 2018,
doi = {https://doi.org/10.1016/j.comgeo.2018.06.002},
abstract = {Let $S$ be a set of $n$ points in the plane in general position
(no three points from $S$ are collinear).
For a positive integer $k$, a \emph{$k$-hole} in $S$ is a convex polygon
with $k$ vertices from~$S$ and no points of~$S$ in its interior.
For a positive integer $l$, a simple polygon~$P$ is \emph{$l$-convex}
if no straight line intersects the interior of~$P$ in more than $l$ connected components.
A point set $S$ is \emph{$l$-convex} if there exists an $l$-convex polygonization of $S$.
Considering a typical Erd{\H{o}}s--Szekeres-type problem, we show that every 2-convex point
set of size~$n$ contains an $\Omega(\log n)$-hole.
In comparison, it is well known that there exist arbitrarily
large point sets in general position with no 7-hole.
Further, we show that our bound is tight by constructing 2-convex point sets with holes
of size at most $O(\log n)$.},
originalfile = {/geometry/cggg.bib}
}
@article{aafpdfuv-cbitcp-18,
author = {Oswin Aichholzer
and Nieves Atienza
and Jos{\'e} M. D{\'i}az-B{\'a}{\~n}ez
and Ruy Fabila-Monroy
and David Flores-Pe{\~n}aloza
and Pablo P{\'e}rez-Lantero
and Jorge Urrutia
and Birgit Vogtenhuber},
title = {{{Computing Balanced Islands in Two Colored Point Sets in the Plane}}},
journal = {Information Processing Letters},
volume = {135},
pages = {28 -- 32},
year = {2018},
issn = {0020-0190},
doi = {https://doi.org/10.1016/j.ipl.2018.02.008},
url = {http://www.sciencedirect.com/science/article/pii/S0020019018300371},
eprint = {1510.01819},
archiveprefix = {arXiv},
abstract = {Let $S$ be a set of $n$ points in general position in the plane,
$r$ of which are red and $b$ of which are blue.
In this paper we present algorithms to find convex sets containing a balanced number of red and blue points.
We provide an $O(n^4)$ time algorithm that for a given $\alpha \in \left [ 0,\frac{1}{2} \right ]$
finds a convex set containing exactly $\lceil \alpha r\rceil$ red points and exactly $\lceil \alpha b \rceil$
blue points of $S$. If $\lceil \alpha r\rceil+\lceil \alpha b\rceil$ is not much larger than
$\frac{1}{3}n$, we improve the running time to $O(n \log n)$.
We also provide an $O(n^2\log n)$ time algorithm to find a convex set containing exactly
$\left \lceil \frac{r+1}{2}\right \rceil$ red points and exactly $\left \lceil \frac{b+1}{2}\right \rceil$
blue points of $S$, and show that balanced islands with more points do not always exist.},
keywords = {Equipartition, Islands, Convex sets, Computational geometry},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{aahpsv-ilbnt-16,
author = {O.~Aichholzer and V.~Alvarez and T.~Hackl and A.~Pilz and B.~Speckmann and B.~Vogtenhuber},
title = {{{An improved lower bound on the number of triangulations}}},
booktitle = {\em Proc. $32^{nd}$ Int. Sympos. Comput. Geom. (SoCG) volume~51 of
Leibniz International Proceedings in Informatics (LIPIcs)},
pages = {7:1--7:16},
year = 2016,
address = {Boston, USA},
category = {3b},
eprint = {},
doi = {10.4230/LIPIcs.SoCG.2016.7},
pdf = {/files/publications/geometry/aahpsv-ilbnt-16.pdf},
thackl_label = {53C},
abstract = {Upper and lower bounds for the number of geometric
graphs of specific types on a given set of points in
the plane have been intensively studied in recent
years. For most classes of geometric graphs it is
now known that point sets in convex position
minimize their number. However, it is still unclear
which point sets minimize the number of geometric
triangulations; the so-called double circles are
conjectured to be the minimizing sets. In this paper
we prove that any set of $n$ points in general
position in the plane has at least $\Omeag(2.631^n)$
geometric triangulations. Our result improves the
previously best general lower bound of $\Omega(2.43^n)$
and also covers the previously best lower bound of
$\Omega(2.63^n)$ for a fixed number of extreme points. We
achieve our bound by showing and combining several
new results, which are of independent interest: 1.
Adding a point on the second convex layer of a given
point set (of $7$ or more points) at least doubles
the number of triangulations. 2. Generalized
configurations of points that minimize the number of
triangulations have at most ${[}n/2{]}$ points on
their convex hull. 3. We provide tight lower
bounds for the number of triangulations of point
sets with up to 15 points. These bounds further
support the double circle conjecture.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{abhkpsvv-slbnh-17,
author = {O.~Aichholzer and M.~Balko and T.~Hackl and J.~Kyn\v{c}l and
I.~Parada and M.~Scheucher and P.~Valtr and B.~Vogtenhuber},
title = {{{A superlinear lower bound on the number of 5-holes}}},
booktitle = {33rd International Symposium on Computational Geometry (SoCG 2017)},
pages = {8:1--8:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
volume = {77},
editor = {Boris Aronov and Matthew J. Katz},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
year = 2017,
address = {Brisbane, Australia},
category = {3b},
eprint = {1703.05253},
archiveprefix = {arXiv},
doi = {10.4230/LIPIcs.SoCG.2017.8},
pdf = {/files/publications/geometry/abhkpsvv-slbnh-17.pdf},
abstract = {Let $P$ be a finite set of points in the plane in
\emph{general position}, that is, no three points of
$P$ are on a common line. We say that a set $H$ of
five points from $P$ is a \emph{$5$-hole in~$P$} if
$H$ is the vertex set of a convex $5$-gon containing
no other points of~$P$. For a positive integer $n$,
let $h_5(n)$ be the minimum number of 5-holes among
all sets of $n$ points in the plane in general
position. Despite many efforts in the last 30
years, the best known asymptotic lower and upper
bounds for $h_5(n)$ have been of order $\Omega(n)$
and~$O(n^2)$, respectively. We show that $h_5(n) =
\Omega(n\log^{4/5}{n})$, obtaining the first
superlinear lower bound on $h_5(n)$. The following
structural result, which might be of independent
interest, is a crucial step in the proof of this
lower bound. If a finite set $P$ of points in the
plane in general position is partitioned by a line
$\ell$ into two subsets, each of size at least 5 and
not in convex position, then $\ell$ intersects the
convex hull of some 5-hole in~$P$. The proof of
this result is computer-assisted.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{abhkpsvv-slbnh-17a,
author = {O.~Aichholzer and M.~Balko and T.~Hackl and J.~Kyn\v{c}l and
I.~Parada and M.~Scheucher and P.~Valtr and B.~Vogtenhuber},
title = {{{A superlinear lower bound on the number of 5-holes}}},
booktitle = {Proc. $33^{rd}$ European Workshop on Computational Geometry EuroCG '17},
pages = {69--73},
year = 2017,
address = {Malm\"o, Sweden},
category = {3b},
eprint = {},
pdf = {/files/publications/geometry/abhkpsvv-slbnh-17a.pdf},
abstract = {Let $P$ be a finite set of points in the plane in
\emph{general position}, that is, no three points of
$P$ are on a common line. We say that a set $H$ of
five points from $P$ is a \emph{$5$-hole in~$P$} if
$H$ is the vertex set of a convex $5$-gon containing
no other points of~$P$. For a positive integer $n$,
let $h_5(n)$ be the minimum number of 5-holes among
all sets of $n$ points in the plane in general
position. Despite many efforts in the last 30
years, the best known asymptotic lower and upper
bounds for $h_5(n)$ have been of order $\Omega(n)$
and~$O(n^2)$, respectively. We show that $h_5(n) =
\Omega(n\log^{4/5}{n})$, obtaining the first
superlinear lower bound on $h_5(n)$. The following
structural result, which might be of independent
interest, is a crucial step in the proof of this
lower bound. If a finite set $P$ of points in the
plane in general position is partitioned by a line
$\ell$ into two subsets, each of size at least 5 and
not in convex position, then $\ell$ intersects the
convex hull of some 5-hole in~$P$. The proof of
this result is computer-assisted.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{aabv-pcmgt-17,
author = {O.~Aichholzer and L.~Andritsch and K.~Baur and B.~Vogtenhuber},
title = {{{Perfect $k$-colored matchings and $k+2$-gonal tilings}}},
booktitle = {Proc. $33^{rd}$ European Workshop on Computational Geometry EuroCG '17},
pages = {81--84},
year = 2017,
address = {Malm\"o, Sweden},
category = {3b},
eprint = {1710.06757},
archiveprefix = {arXiv},
pdf = {/files/publications/geometry/aabv-pcmgt-17.pdf},
abstract = { We derive a simple bijection between geometric plane perfect
matchings on $2n$ points in convex position and triangulations on
$n+2$ points in convex position. We then extend this bijection to
monochromatic plane perfect matchings on periodically $k$-colored
vertices and $(k+2)$-gonal tilings of convex point sets. These
structures are related to Temperley-Lieb algebras and our bijections
provide explicit one-to-one relations between matchings and tilings.
Moreover, for a given element of one class, the corresponding
element of the other class can be computed in linear time.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{aafmm-bdk-17,
author = {Bernardo M. {\'A}brego and Oswin Aichholzer and Silvia Fern{\'a}ndez-Merchant and
Dan McQuillan and Bojan Mohar and Petra Mutzel and Pedro Ramos and R. Bruce Richter and Birgit Vogtenhuber},
title = {{{Bishellable drawings of $K_n$}}},
booktitle = {Proc. XVII Encuentros de Geometr\'{\i}a Computacional},
category = {3b},
pages = {17--20},
pdf = {/files/publications/geometry/aafmm-bdk-17.pdf},
year = 2017,
address = {Alicante, Spain},
eprint = {1510.00549},
abstract = {In this work, we generalize the concept of
$s$-shellability to bishellability, where the former
implies the latter in the sense that every
$s$-shellable drawing is, for any $b \leq s-2$, also
$b$-bishellable. Our main result is that
$(\lfloor \frac{n}{2} \rfloor\!-\!2)$-bishellability
also guarantees, with a simpler proof than for
$s$-shellability, that a drawing has at least
$H(n)$ crossings. We exhibit a drawing of $K_{11}$
that has $H(11)$ crossings, is 3-bishellable, and is
not $s$-shellable for any $s\geq5$. This shows that
we have properly extended the class of drawings for
which the Harary-Hill Conjecture is proved.},
originalfile = {/geometry/cggg.bib}
}
@article{aafmm-bdk-18,
author = {Bernardo M. {\'A}brego and Oswin Aichholzer and Silvia Fern{\'a}ndez-Merchant and
Dan McQuillan and Bojan Mohar and Petra Mutzel and Pedro Ramos and R. Bruce Richter and Birgit Vogtenhuber},
title = {{{Bishellable drawings of {$K_n$}}}},
noshortjournal = {SIAM J. Discrete Math.},
journal = {SIAM Journal on Discrete Mathematics},
volume = {32},
number = {4},
pages = {2482--2492},
year = {2018},
doi = {10.1137/17M1147974},
eprint = {1510.00549},
archiveprefix = {arXiv},
abstract = {{The Harary--Hill conjecture, still open after more than 50 years,
asserts that the crossing number of the complete graph $K_n$ is
$H(n) := \frac 1 4 \left\lfloor\frac{\mathstrut n}{\mathstrut 2}\right\rfloor
\left\lfloor\frac{\mathstrut n-1}{\mathstrut 2}\right\rfloor
\left\lfloor\frac{\mathstrut n-2}{\mathstrut 2}\right\rfloor
\left\lfloor\frac{\mathstrut n-3}{\mathstrut 2}\right\rfloor\,.$
\'Abrego et al. [B.~M. {\'{A}}brego, O. Aichholzer, S. Fern{\'{a}}ndez{-}Merchant,
P. Ramos, and G. Salazar. Shellable drawings and the cylindrical crossing number of
$K_n$. {\em Disc. {\&} Comput. Geom.}, 52(4):743--753, 2014.]
introduced the notion of shellability of a drawing $D$ of $K_n$.
They proved that if $D$ is $s$-shellable for some $s\geq\lfloor\frac{n}{2}\rfloor$,
then $D$ has at least $H(n)$ crossings.
This is the first combinatorial condition on a drawing
that guarantees at least $H(n)$ crossings.
In this work, we generalize the concept of $s$-shellability to bishellability,
where the former implies the latter in the sense that every $s$-shellable drawing is,
for any $b \leq s-2$, also \mbox{$b$-bishellable}.
Our main result is that $(\lfloor \frac{n}{2} \rfloor\!-\!2)$-bishellability of a drawing
$D$ of $K_n$ also guarantees, with a simpler proof than for \mbox{$s$-shellability},
that $D$ has at least $H(n)$ crossings.
We exhibit a drawing of $K_{11}$ that has $H(11)$ crossings, is 3-bishellable, and is not
$s$-shellable for any $s\geq5$.This shows that we have properly extended the class of
drawings for which the Harary--Hill Conjecture is proved. Moreover, we provide an infinite
family of drawings of $K_n$ that are $(\lfloor \frac{n}{2} \rfloor\!-\!2)$-bishellable,
but not $s$-shellable for any $s\geq\lfloor\frac{n}{2}\rfloor$.}},
originalfile = {/geometry/cggg.bib}
}
@article{abhpv-ltdbm-17,
author = {Oswin Aichholzer and Luis Barba and Thomas Hackl and Alexander Pilz and Birgit Vogtenhuber},
title = {{{Linear Transformation Distance for Bichromatic
Matchings}}},
journal = {Computational Geometry: Theory and Applications},
year = 2018,
volume = {68},
pages = {77--88},
category = {3a},
doi = {http://dx.doi.org/10.1016/j.comgeo.2017.05.003},
arxiv = {1312.0884v1},
note = {Special Issue in Memory of Ferran Hurtado},
issn = {0925-7721},
url = {http://www.sciencedirect.com/science/article/pii/S0925772117300366},
pdf = {/files/publications/geometry/abhpv-ltdbm-17.pdf},
abstract = {Let $P=B\cup R$ be a set of $2n$ points in general
position, where $B$ is a set of $n$ blue points and
$R$ a set of $n$ red points. A \emph{$BR$-matching}
is a plane geometric perfect matching on $P$ such
that each edge has one red endpoint and one blue
endpoint. Two $BR$-matchings are compatible if their
union is also plane.\\ The \emph{transformation
graph of $BR$-matchings} contains one node for each
$BR$-matching and an edge joining two such nodes if
and only if the corresponding two $BR$-matchings are
compatible. In SoCG 2013 it has been shown by
Aloupis, Barba, Langerman, and Souvaine that this
transformation graph is always connected, but its
diameter remained an open question. In this paper we
provide an alternative proof for the connectivity of
the transformation graph and prove an upper bound of
$2n$ for its diameter, which is asymptotically
tight.},
originalfile = {/geometry/cggg.bib}
}
@article{affhhuv-mimp-17,
author = {Oswin Aichholzer and Ruy Fabila-Monroy and David Flores-Pe{\~n}aloza and Thomas Hackl and Jorge Urrutia and Birgit Vogtenhuber},
title = {{{Modem Illumination of Monotone Polygons}}},
journal = {Computational Geometry: Theory and Applications},
year = 2018,
volume = {68},
number = {},
pages = {101--118},
category = {3a},
doi = {https://doi.org/10.1016/j.comgeo.2017.05.010},
arxiv = {1503.05062},
note = {Special Issue in Memory of Ferran Hurtado},
issn = {0925-7721},
url = {http://www.sciencedirect.com/science/article/pii/S0925772117300433},
abstract = {We study a generalization of the classical problem of
illumination of polygons. Instead of modeling a light
source we model a wireless device whose radio signal can
penetrate a given number $k$ of walls. We call these
objects $k$-modems and study the minimum number of
$k$-modems necessary to illuminate monotone and monotone
orthogonal polygons. We show that every monotone polygon on
$n$ vertices can be illuminated with $\left\lceil
\frac{n}{2k} \right\rceil$ $k$-modems and exhibit examples
of monotone polygons requiring $\left\lceil \frac{n}{2k+2}
\right\rceil$ $k$-modems. For monotone orthogonal polygons,
we show that every such polygon on $n$ vertices can be
illuminated with $\left\lceil \frac{n}{2k+4} \right\rceil$
$k$-modems and give examples which require $\left\lceil
\frac{n}{2k+4} \right\rceil$ $k$-modems for $k$ even and
$\left\lceil \frac{n}{2k+6} \right\rceil$ for $k$ odd.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{bckmrrssvw-rpd-17b,
author = {Bahareh Banyassady and Man-Kwun Chiu and Matias Korman and Wolfgang Mulzer and Andr{\'e} van Renssen and Marcel Roeloffzen and Paul Seiferth and Yannik Stein and Birgit Vogtenhuber and Max Willert},
title = {{{Routing in Polygonal Domains}}},
booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)},
pages = {10:1--10:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
isbn = {978-3-95977-054-5},
issn = {1868-8969},
year = {2017},
volume = {92},
editor = {Yoshio Okamoto and Takeshi Tokuyama},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
url = {http://drops.dagstuhl.de/opus/volltexte/2017/8237},
urn = {urn:nbn:de:0030-drops-82379},
doi = {10.4230/LIPIcs.ISAAC.2017.10},
annote = {Keywords: polygonal domains, routing scheme, small stretch,Yao graph},
abstract = {We consider the problem of routing a data packet through
the visibility graph of a polygonal domain $P$ with $n$
vertices and $h$ holes. We may preprocess $P$ to obtain
a \emph{label} and a \emph{routing table} for each vertex.
Then, we must be able to route a data packet between
any two vertices $p$ and $q$ of $P$, where each step
must use only the label of the target node $q$
and the routing table of the current node.
For any fixed $\varepsilon > 0$,
we present a routing scheme that always achieves
a routing path that exceeds the shortest path by
a factor of at most $1 + \varepsilon$.
The labels have $\mathcal{O}(\log n)$ bits, and the
routing tables are of size $\mathcal{O}((\varepsilon^{-1}+h)\log n)$.
The preprocessing time is $\mathcal{O}(n^2\log n + hn^2+\varepsilon^{-1}hn)$.
It can be improved to $\mathcal{O}(n^2+\varepsilon^{-1}n)$ for
simple polygons.
},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{cfmtv-igrgs-17,
author = {Cardinal, Jean
and Felsner, Stefan
and Miltzow, Tillmann
and Tompkins, Casey
and Vogtenhuber, Birgit},
editor = {Bodlaender, Hans L.
and Woeginger, Gerhard J.},
title = {{"Intersection Graphs of Rays and Grounded Segments"}},
booktitle = {Graph-Theoretic Concepts in Computer Science (WG 2017)},
year = {2017},
publisher = {Springer International Publishing},
address = {Cham},
pages = {153--166},
note = {Revised Selected Papers},
abstract = {We consider several classes of intersection graphs of line segments in the plane and prove new equality and separation results between those classes. In particular, we show that: intersection graphs of grounded segments and intersection graphs of downward rays form the same graph class, not every intersection graph of rays is an intersection graph of downward rays, and not every outer segment graph is an intersection graph of rays. },
isbn = {978-3-319-68705-6},
doi = {https://doi.org/10.1007/978-3-319-68705-6_12},
originalfile = {/geometry/cggg.bib}
}
@article{bfv-nmfc-15,
author = {Imre B{\'a}r{\'a}ny and Ruy Fabila-Monroy and Birgit Vogtenhuber},
title = {{{{$(n,m)$}-Fold Covers of Spheres}}},
journal = {Proceedings of the Steklov Institute of Mathematics},
volume = {288},
pages = {203--208},
year = 2015,
eprint = {1410.0056},
doi = {http://dx.doi.org/10.1134/S0081543815010150},
originalfile = {/geometry/cggg.bib}
}
@article{cfmtv-igrgs-18,
title = {{{Intersection Graphs of Rays and Grounded Segments}}},
author = {Jean Cardinal and Stefan Felsner and Tillmann Miltzow and Casey Tompkins and Birgit Vogtenhuber},
journal = {Journal of Graph Algorithms and Applications},
volume = {22},
number = {2},
pages = {273--295},
year = {2018},
doi = {10.7155/jgaa.00470},
__note = {{Full version also available at \url{www.arxiv.org/abs/1612.03638}}},
eprint = {1612.03638},
abstract = { We consider several classes of intersection graphs of line segments in the plane and prove new equality and separation results between those classes.
In particular, we show that:
\begin{itemize}
\item intersection graphs of grounded segments and intersection graphs of downward rays form the same graph class,
\item not every intersection graph of rays is an intersection graph of downward rays, and
\item not every outer segment graph is an intersection graph of rays.
\end{itemize}
The first result answers an open problem posed by Cabello and Jej\v{c}i\v{c}. The third result confirms a conjecture by Cabello.
We thereby completely elucidate the remaining open questions on the containment relations between these classes of segment graphs.
We further characterize the complexity of the recognition problems for the classes of outer segment, grounded segment, and ray intersection graphs.
We prove that these recognition problems are complete for the existential theory of the reals.
This holds even if a 1-string realization is given as additional input.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{cgknov-erdf-15,
author = {Jurek Czyzowicz and Konstantinos Georgiou and Evangelos Kranakis and Lata Narayanan and Jarda Opatrny and Birgit Vogtenhuber},
title = {{{Evacuating Robots from a Disk Using Face-to-Face Communication (Extended Abstract)}}},
booktitle = {Algorithms and Complexity. CIAC 2015.},
pages = {140--152},
year = 2015,
address = {Paris, France},
series = {Lecture Notes in Computer Science (LNCS)},
volume = {9079},
publisher = {Springer},
address = {Cham},
editor = {V. Paschos and P. Widmayer},
eprint = {1501.04985},
archiveprefix = {arXiv},
doi = {http://dx.doi.org/10.1007/978-3-319-18173-8_10},
originalfile = {/geometry/cggg.bib}
}
@article{cgknov-erdf-20,
title = {{{Evacuating Robots from a Disk Using Face-to-Face Communication}}},
author = {Czyzowicz, Jurek and Georgiou, Konstantinos and Kranakis, Evangelos and Narayanan, Lata and Opatrny, Jarda and Vogtenhuber, Birgit},
url = {https://dmtcs.episciences.org/6732},
journal = {Discrete Mathematics \& Theoretical Computer Science},
volume = {22},
number = {4},
year = {2020},
eprint = {1501.04985},
abstract = {Assume that two robots are located at the centre of a unit disk.
Their goal is to \emph{evacuate} from the disk
through an \emph{exit} at an unknown location on the boundary of the disk.
At any time the robots can move anywhere they choose on the disk, independently of each other, with maximum speed $1$.
The robots can cooperate by exchanging information
whenever they meet.
We study algorithms for the two robots to minimize the \emph{evacuation time}: the time when \emph{both} robots reach the exit.
Czyzowicz et al.~(2014) gave an algorithm defining trajectories for the two
robots yielding evacuation time at most $5.740$ and also proved that any algorithm has evacuation time at least $3+ \frac{\pi}{4} + \sqrt{2} \approx 5.199$.
We improve both the upper and lower bound on the evacuation time of a unit disk.
Namely, we present a new non-trivial algorithm whose evacuation time is at most $5.628$
and show that any algorithm has evacuation time at least $3+ \frac{\pi}{6} + \sqrt{3} \approx 5.255$.
To achieve the upper bound, we designed an algorithm which proposes a forced meeting between the two robots, even if the exit has not been found by either of them. We also show that such a strategy is provably optimal for a related problem of searching for an exit placed at the vertices of a regular hexagon.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{kklnsv-ldkl-17,
author = {Philipp Kindermann and Stephen Kobourov and Maarten L{\"o}ffler and Martin N{\"o}llenburg and Andr{\'e} Schulz and Birgit Vogtenhuber},
title = {{{Lombardi Drawings of Knots and Links}}},
booktitle = {Graph Drawing and Network Visualization. GD 2017.},
nonote = {25th International Symposium on Graph Drawing and Network Visualization},
pages = {113--126},
address = {Boston, MA, USA},
note = {Revised Selected Papers},
year = 2018,
publisher = {Springer, Cham},
editor = {Fabrizio Frati and Kwan-Liu Ma},
doi = {https://doi.org/10.1007/978-3-319-73915-1_10},
isbn = {978-3-319-73914-4},
e-isbn = {978-3-319-73915-1},
eprint = {1708.09819},
archiveprefix = {arXiv},
abstract = {Knot and link diagrams are projections of one or more 3-dimensional simple closed curves into
${{\sf l} \kern -.10em {\sf R} }^2$, such that no more than two points
project to the same point in ${{\sf l} \kern -.10em {\sf R} }^2$.
These diagrams are
drawings of 4-regular plane multigraphs.
Knots are typically smooth curves in ${{\sf l} \kern -.10em {\sf R} }^3$, so their projections should be smooth curves in ${{\sf l} \kern -.10em {\sf R} }^2$ with good continuity and large crossing angles: exactly the properties of Lombardi graph drawings (defined by circular-arc edges and perfect angular resolution).
We show that several knots do not allow plane Lombardi drawings. On the other hand, we identify a large class of 4-regular plane multigraphs that do have Lombardi drawings.
We then study two relaxations of Lombardi drawings and
show that every knot
admits a plane 2-Lombardi drawing (where edges are composed of two circular arcs).
Further, every knot
is \emph{near-Lombardi}, that is, it can be drawn as Lombardi drawing when
relaxing the angular resolution requirement by an arbitrary small angular offset~$\varepsilon$, while maintaining a $180^\circ$ angle between opposite edges. },
originalfile = {/geometry/cggg.bib}
}
@article{kklnsv-ldkl-19,
author = {Philipp Kindermann and Stephen Kobourov and Maarten L{\"o}ffler and Martin N{\"o}llenburg and Andr{\'e} Schulz and Birgit Vogtenhuber},
title = {{{Lombardi Drawings of Knots and Links}}},
journal = {Journal of Computational Geometry},
pages = {444--476},
year = 2019,
volume = 10,
number = 1,
doi = {https://doi.org/10.20382/jocg.v10i1a15},
eprint = {1708.09819},
abstract = {Knot and link diagrams are projections of one or more 3-dimensional simple closed curves into
${{\sf l} \kern -.10em {\sf R} }^2$, such that no more than two points
project to the same point in ${{\sf l} \kern -.10em {\sf R} }^2$.
These diagrams are
drawings of 4-regular plane multigraphs.
Knots are typically smooth curves in ${{\sf l} \kern -.10em {\sf R} }^3$, so their projections should be smooth curves in ${{\sf l} \kern -.10em {\sf R} }^2$ with good continuity and large crossing angles: exactly the properties of Lombardi graph drawings (defined by circular-arc edges and perfect angular resolution).
We show that several knots do not allow crossing-minimal plane Lombardi drawings. On the other hand, we identify a large class of 4-regular plane multigraphs that do have plane Lombardi drawings.
We then study two relaxations of Lombardi drawings and
show that every knot
admits a crossing-minimal plane 2-Lombardi drawing (where edges are composed of two circular arcs).
Further, every knot
is \emph{near-Lombardi}, that is, it can be drawn as a plane Lombardi drawing when
relaxing the angular resolution requirement by an arbitrary small angular offset~$\varepsilon$, while maintaining a $180^\circ$ angle between opposite edges.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{kmrrssvw-rsp-17,
author = {Matias Korman and Wolfgang Mulzer and Andr{\'e} van Renssen and Marcel Roeloffzen and Paul Seiferth and Yannik Stein and Birgit Vogtenhuber and Max Willert},
title = {{{Routing in Simple Polygons}}},
booktitle = {Proc. {$33^{rd}$} European Workshop on Computational Geometry EuroCG '17},
year = 2017,
address = {Malm{\"o}, Sweden},
pages = {17--20},
abstract = {{A routing scheme $R$ in a network $G=(V,E)$ is an algorithm
that allows to send messages from one node to another in the network.
We are first allowed a preprocessing phase in which we assign a unique
\emph{label} to each node $p\in V$ and a \emph{routing table} with additional
information. After this preprocessing, the routing algorithm itself must be
local (i.e., we can only use the information from the label of the target
and the routing table of the node that we are currently at).
We present a routing scheme for routing in simple
polygons: for any $\varepsilon > 0$ the routing
scheme provides a stretch of $1+\varepsilon$, labels have $O(\log n)$ bits, the
corresponding routing tables are of size
$O(\varepsilon^{-1}\log n)$, and the preprocessing time
is $O(n^2+\varepsilon^{-1}n)$. This improves the best known strategies for
general graphs by Roditty and Tov (Distributed Computing 2016).}},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{bkmrrssvw-rpd-17a,
author = {Bahareh Banyassady and Matias Korman and Wolfgang Mulzer and Andr\'e van Renssen
and Marcel Roeloffzen and Paul Seiferth and Yannik Stein and Birgit Vogtenhuber and Max Willert},
title = {{{Routing in Polygonal Domains}}},
booktitle = {Proc. of the $20^{th}$ Japan Conference on Discrete and
Computational Geometry, Graphs, and Games (JCDCG$^3$ 2017)},
year = 2017,
pages = {88--89},
address = {Tokyo, Japan},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{abhkmppsvvw-mggrot-18,
author = {Oswin Aichholzer and
Martin Balko and
Michael Hoffmann and
Jan Kyn\v{c}l and
Wolfgang Mulzer and
Irene Parada and
Alexander Pilz and
Manfred Scheucher and
Pavel Valtr and
Birgit Vogtenhuber and
Emo Welzl},
title = {{{Minimal Geometric Graph Representations of Order Types}}},
booktitle = {Proc. {$34^{th}$} European Workshop on Computational Geometry EuroCG '18},
year = 2018,
pages = {21:1--21:6},
address = {Berlin, Germany},
abstract = {We consider the problem of characterizing small geometric graphs
whose structure uniquely determines the order type of its vertex set.
We describe a set of edges that prevent the order type from changing
by continuous movement and identify properties of the resulting graphs.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{aktv-npmt-18,
author = {Oswin Aichholzer and
Michael Kerber and
Istv{\'a}n Talata and
Birgit Vogtenhuber},
title = {{{A Note on Planar Monohedral Tilings}}},
booktitle = {Proc. {$34^{th}$} European Workshop on Computational Geometry EuroCG '18},
year = 2018,
pages = {31:1--31:6},
address = {Berlin, Germany},
abstract = {{A planar \emph{monohedral tiling} is a decomposition of $\mathbb{R}^2$
into congruent \emph{tiles}.
We say that such a tiling has the \emph{flag property} if for each triple
of tiles that intersect pairwise, the three tiles intersect in a common point.
We show that for convex tiles, there exist only three classes of tilings
that are not flag, and they all consist of triangular tiles; in particular,
each convex tiling using polygons with $n\geq 4$ vertices is flag.
We also show that an analogous statement for the case of non-convex tiles
is not true by presenting a family of counterexamples.}},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{amsv-mcsig-18,
author = {Oswin Aichholzer and
Wolfgang Mulzer and
Partick Schnider and
Birgit Vogtenhuber},
title = {{{NP-Completeness of Max-Cut for Segment Intersection Graphs}}},
booktitle = {Proc. {$34^{th}$} European Workshop on Computational Geometry EuroCG '18},
year = 2018,
pages = {32:1-32:6},
address = {Berlin, Germany},
abstract = {{We consider the problem of finding a \emph{maximum cut} in a graph $G = (V, E)$,
that is, a partition $ V_1 \dot\cup V_2$ of $V$ such that the number of edges between $V_1$ and $V_2$ is maximum.
It is well known that the decision problem whether $G$ has a cut of at least a given size is in general NP-complete.
We show that this problem remains hard when restricting the input to \emph{segment intersection graphs}.
These are graphs whose vertices can be drawn as straight-line segments,
where two vertices share an edge if and only if the corresponding segments intersect.
We obtain our result by a reduction from a variant of \textsc{Planar Max-2-SAT}
that we introduce and also show to be NP-complete.}},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{aepv-assdcg-17,
author = {Oswin Aichholzer and
Florian Ebenf\"{u}hrer and
Irene Parada and
Alexander Pilz and
Birgit Vogtenhuber},
title = {{{On semi-simple drawings of the complete graph}}},
booktitle = {Proc. XVII Encuentros de Geometr\'{\i}a Computacional},
pages = {25--28},
year = 2017,
address = {Alicante, Spain},
pdf = {/files/publications/geometry/aepv-assdcg-17.pdf},
abstract = {In this work we study rotation systems and semi-simple drawings of $K_n$. A simple drawing of a graph is a drawing in which every pair of edges intersects in at most one point. In a semi-simple drawing, edge pairs might intersect in multiple points, but incident edges only intersect in their common endpoint. A rotation system is called (semi-)realizable if it can be realized with a (semi-)simple drawing. It is known that a rotation system is realizable if and only if all its 5-tuples are realizable. For the problem of characterizing semi-realizability, we present a rotation system with six vertices that is not semi-realizable, although all its 5-tuples are semi-realizable. Moreover, by an exhaustive computer search, we show that also for seven vertices there exist minimal not semi-realizable rotation systems (that is, rotation systems in which all proper sub-rotation systems are semi-realizable). This indicates that checking semi-realizability is harder than checking realizability. Finally we show that for semi-simple drawings, generalizations of Conway's Thrackle Conjecture and the conjecture on the existence of plane Hamiltonian cycles do not hold.},
originalfile = {/geometry/cggg.bib}
}
@article{aabv-pcmgt-18,
author = {Oswin Aichholzer and Lukas Andritsch and Karin Baur and Birgit Vogtenhuber},
title = {{{Perfect $k$-Colored Matchings and $(k+2)$-Gonal Tilings}}},
journal = {Graphs and Combinatorics},
issn = {0911-0119},
publisher = {Springer Japan},
pages = {1333--1346},
volume = {34},
number = {6},
doi = {https://doi.org/10.1007/s00373-018-1967-8},
url = {http://link.springer.com/article/10.1007/s00373-018-1967-8},
year = 2018,
eprint = {1710.06757},
archiveprefix = {arXiv},
abstract = {We derive a simple bijection between geometric plane perfect matchings on $2n$ points in convex position and triangulations on $n+2$ points in convex position. We then extend this bijection to monochromatic plane perfect matchings on periodically $k$-colored vertices and $(k+2)$-gonal tilings of convex point sets. These structures are related to a generalization of Temperley–Lieb algebras and our bijections provide explicit one-to-one relations between matchings and tilings. Moreover, for a given element of one class, the corresponding element of the other class can be computed in linear time.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{iv-dtd-18,
author = {John Iacono and Birgit Vogtenhuber},
title = {{{In pursuit of a dynamic tree decomposition}}},
booktitle = {Proceedings of the of the 21st Japan Conference on Discrete and
Computational Geometry, Graphs, and Games (JCDCG\^{}3$\,$2018)},
year = 2018,
pages = {23--25},
address = {Manila, Philippines},
abstract = {Treewidth is a measure of a graph's similarity to a tree.
Since its introduction \cite{DBLP:journals/jal/RobertsonS86},
it has gained wide popularity as many problems can be solved much
faster under the assumption of bounded treewidth. The definition of
treewidth depends on the existence of a structure known as a tree
decomposition, and many treewidth dependent algorithms begin by
constructing this decomposition. One natural question is: can a tree
decomposition of small width be maintained under dynamic changes in
the graph?We examine a restricted class of graphs whereby the tree
decomposition can be computed in linear time, and show that for such
a class of graphs it can be maintained dynamically.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{adhopvv-estg-19,
author = {Oswin Aichholzer and Jos{\'e} Miguel D\'{\i}az-B{\'a}{\~n}ez and Thomas Hackl and David Orden and Alexander Pilz and Inmaculada Ventura and Birgit Vogtenhuber},
title = {{{Erd{\H{o}}s-Szekeres-Type Games}}},
booktitle = {Proc. {$35^{th}$} European Workshop on Computational Geometry EuroCG '19},
year = 2019,
pages = {23:1-23:7},
address = {Utrecht, The Netherlands},
pdf = {/files/publications/geometry/adhopvv-estg-19.pdf},
url = {http://www.eurocg2019.uu.nl/papers/23.pdf},
abstract = {{We consider several combinatorial games, inspired by the Erd{\H{o}}s-Szekeres theorem that states the
existence of a convex $k$-gon in every sufficiently large point set. Two players take turns to place
points in the Euclidean plane and the game is over as soon as the first $k$-gon appears. In the
Maker-Maker setting the player who placed the last point wins, while in the Avoider-Avoider
version this player loses. Combined versions like Maker-Breaker are also possible. Moreover,
variants can be obtained by considering that (1) the points to be placed are either uncolored or
bichromatic, (2) both players have their own color or can play with both colors, (3) the
$k$-gon must be empty of other points, or (4) the $k$-gon has to be convex.}},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{affhpvz-ccn-19,
author = {Oswin Aichholzer and Ruy Fabila Monroy and Adrian Fuchs and Carlos Hidalgo Toscano and Irene Parada and Birgit Vogtenhuber and Francisco Zaragoza},
title = {{{On the 2-Colored Crossing Number}}},
booktitle = {Proc. {$35^{th}$} European Workshop on Computational Geometry EuroCG '19},
year = 2019,
pages = {56:1-56:7},
address = {Utrecht, The Netherlands},
pdf = {/files/publications/geometry/affhpvz-ccn-19.pdf},
url = {http://www.eurocg2019.uu.nl/papers/56.pdf},
abstract = {{Let $D$ be a straight-line drawing of a graph where every edge is colored with one of two possible
colors. The rectilinear 2-colored crossing number of $D$ is the minimum number of crossings
between edges of the same color, taken over all possible colorings of $D$. We show lower and upper
bounds on the rectilinear 2-colored crossing number for the complete graph $K_n$. Moreover, for
fixed drawings of $K_n$ we give bounds on the relation between its rectilinear 2-colored crossing
number and its rectilinear crossing number.}},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{apsvw-sssdk-19,
author = {Oswin Aichholzer and Irene Parada and Manfred Scheucher and Birgit Vogtenhuber and Alexandra Weinberger},
title = {{{Shooting Stars in Simple Drawings of $K_{m,n}$}}},
booktitle = {Proc. {$35^{th}$} European Workshop on Computational Geometry EuroCG '19},
year = 2019,
pages = {59:1-59:6},
address = {Utrecht, The Netherlands},
pdf = {/files/publications/geometry/apsvw-sssdk-19.pdf},
url = {http://www.eurocg2019.uu.nl/papers/59.pdf},
eprint = {2209.01190},
archiveprefix = {arXiv},
abstract = {{In this work we study the existence of plane spanning trees in simple drawings of the complete
bipartite graph $K_{m,n}$. We show that every simple drawing of $K_{2,n}$ and $K_{3,n}$, $n \geq 1$, as well as
every outer drawing of $K_{m,n}$ for any $m,n \geq 1$, contains plane spanning trees. Moreover, for all
these cases we show the existence of special plane spanning trees, which we call shooting stars.
Shooting stars are spanning trees that contain the star of a vertex, i.e., all its incident edges.}},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{aappttuv-hmpcb-19,
author = {Oswin Aichholzer and Carlos Alegr\'{i}a Galicia and Irene Parada and Alexander Pilz and Javier Tejel and Csaba D. T\'{o}th and Jorge Urrutia and Birgit Vogtenhuber},
title = {{{Hamiltonian meander paths and cycles on bichromatic point sets}}},
booktitle = {Proc. XVIII Encuentros de Geometr\'{\i}a Computacional},
pages = {35--38},
year = 2019,
address = {Girona, Spain},
pdf = {/files/publications/geometry/aappttuv-hmpcb-19.pdf},
url = {http://imae.udg.edu/egc2019/doc/BookAbstractsEGC2019.pdf},
abstract = {We show that any set of $n$ blue and $n$ red points on a
line admits a plane meander path, that is, a crossing-free
panning path that passes across the line on red
and blue points in alternation. For meander cycles,
we derive tight bounds on the minimum number of
necessary crossings which depend on the coloring of
the points. Finally, we provide some relations for the
number of plane meander paths.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{aappttuv-hmpcb2-19,
author = {Oswin Aichholzer and Carlos Alegr\'{i}a Galicia and Irene Parada and Alexander Pilz and Javier Tejel and Csaba D. T\'{o}th and Jorge Urrutia and Birgit Vogtenhuber},
title = {{{Hamiltonian meander paths and cycles on bichromatic point sets}}},
booktitle = {EasyChair Preprint no. 3130},
year = 2019,
url = {https://easychair.org/publications/preprint/N7TX},
abstract = {We show that any set of $n$ blue and $n$ red points on a
line admits a plane meander path, that is, a crossing-free
panning path that passes across the line on red
and blue points in alternation. For meander cycles,
we derive tight bounds on the minimum number of
necessary crossings which depend on the coloring of
the points. Finally, we provide some relations for the
number of plane meander paths.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{affhpvz-ccn-19b,
author = {Oswin Aichholzer and Ruy Fabila-Monroy and Adrian Fuchs and Carlos Hidalgo-Toscano and Irene Parada and Birgit Vogtenhuber and Francisco Zaragoza},
title = {{{On the 2-colored crossing number}}},
booktitle = {Graph Drawing and Network Visualization. GD 2019},
nonote = {27th International Symposium on Graph Drawing and Network Visualization},
series = {Lecture Notes in Computer Science (LNCS)},
volume = {11904},
pages = {87--100},
address = {Prague, Czechia},
year = 2019,
eprint = {1908.06461},
archiveprefix = {arXiv},
doi = {https://doi.org/10.1007/978-3-030-35802-0_7},
abstract = {Let $D$ be a straight-line drawing of a graph.
The rectilinear 2-colored crossing number of $D$ is the minimum number of crossings between edges of the same color,
taken over all possible 2-colorings of the edges of $D$.
First, we show lower and upper bounds on the rectilinear 2-colored crossing number for the complete graph $K_n$.
To obtain this result, we prove that asymptotic bounds can be derived from optimal and near-optimal instances with few vertices.
We obtain such instances using a combination of heuristics and integer programming.
Second, for any fixed drawing of $K_n$,
we improve the bound on the ratio between its rectilinear 2-colored crossing number and its rectilinear crossing number.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{abhkmppsvvw-mrotg-19,
author = {Oswin Aichholzer and Martin Balko and Michael Hoffmann and Jan Kyn\v{c}l and Wolfgang Mulzer and Irene Parada and Alexander Pilz and Manfred Scheucher and Pavel Valtr and Birgit Vogtenhuber and Emo Welzl},
title = {{{Minimal representations of order types by geometric graphs}}},
booktitle = {Graph Drawing and Network Visualization. GD 2019},
nonote = {27th International Symposium on Graph Drawing and Network Visualization},
series = {Lecture Notes in Computer Science (LNCS)},
volume = {11904},
pages = {101--113},
address = {Prague, Czechia},
year = 2019,
eprint = {1908.05124},
doi = {https://doi.org/10.1007/978-3-030-35802-0_8},
abstract = {In order to have a compact visualization of the order type of
a given point set $S$,
we are interested in geometric graphs on $S$ with few edges that unequivocally display %
the order type of $S$.
We introduce the concept of \emph{exit edges},
which prevent the order type from changing under continuous motion of vertices.
Exit edges have a natural dual characterization,
which allows us to efficiently compute them and to bound their number.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{akopprv-gwlta-19b,
author = {Oswin Aichholzer and Matias Korman and Yoshio Okamoto and Irene Parada and Daniel Perz and Andr\'e van Renssen and Birgit Vogtenhuber},
title = {{{Graphs with large total angular resolution}}},
booktitle = {Graph Drawing and Network Visualization. GD 2019},
nonote = {27th International Symposium on Graph Drawing and Network Visualization},
series = {Lecture Notes in Computer Science (LNCS)},
volume = {11904},
pages = {193--199},
address = {Prague, Czechia},
year = 2019,
eprint = {1908.06504},
archiveprefix = {arXiv},
doi = {https://doi.org/10.1007/978-3-030-35802-0_15},
isbn = {978-3-030-35802-0},
abstract = {The total angular resolution of a straight-line drawing is the minimum angle between two edges of the drawing.
It combines two properties contributing to the readability of a drawing:
the angular resolution, that is the minimum angle between incident edges,
and the crossing resolution, that is the minimum angle between crossing edges.
We consider the total angular resolution of a graph,
which is the maximum total angular resolution of a straight-line drawing of this graph.
We prove that, up to a finite number of well specified exceptions of constant size,
the number of edges of a graph with $n$ vertices and a total angular resolution greater than $60^{\circ}$ is bounded by $2n-6$.
This bound is tight.
In addition, we show that deciding whether a graph has total angular resolution at least $60^{\circ}$ is \NP-hard.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{akksv-evrmt-19,
author = {Oswin Aichholzer and Linda Kleist and Boris Klemz and Felix Schr\"oder and Birgit Vogtenhuber},
title = {{{On the Edge-Vertex Ratio of Maximal Thrackles}}},
booktitle = {Graph Drawing and Network Visualization. GD 2019},
nonote = {27th International Symposium on Graph Drawing and Network Visualization},
series = {Lecture Notes in Computer Science (LNCS)},
volume = {11904},
pages = {482--495 },
address = {Prague, Czechia},
year = 2019,
eprint = {1908.08857},
doi = {https://doi.org/10.1007/978-3-030-35802-0_37},
abstract = {A drawing of a graph in the plane is a \emph{thrackle} if every pair of edges intersects exactly once,
either at a common vertex or at a proper crossing. Conway's conjecture states that a thrackle has at most as many edges as vertices.
In this paper, we investigate the edge-vertex ratio of \emph{maximal thrackles}, that is, thrackles in which no edge between already
existing vertices can be inserted such that the resulting drawing remains a thrackle. For maximal geometric and topological thrackles,
we show that the edge-vertex ratio can be arbitrarily small. When forbidding isolated vertices, the edge-vertex ratio of maximal
geometric thrackles can be arbitrarily close to the natural lower bound of $\frac{1}{2}$. For maximal topological thrackles without
isolated vertices, we present an infinite family with an edge-vertex ratio arbitrary close to~$\frac{4}{5}$.},
originalfile = {/geometry/cggg.bib}
}
@article{ahkprrrv-ppsgs-19,
author = {Oswin Aichholzer and Thomas Hackl and Matias Korman and Alexander Pilz and Andr{\'e} van Renssen and Marcel Roeloffzen and G\"unter Rote and Birgit Vogtenhuber},
title = {{{Packing plane spanning graphs with short edges in complete geometric graphs}}},
journal = {Computational Geometry},
volume = {782},
pages = {1--15},
year = {2019},
issn = {0925-7721},
doi = {https://doi.org/10.1016/j.comgeo.2019.04.001},
url = {http://www.sciencedirect.com/science/article/pii/S0925772119300495},
pdf = {/files/publications/geometry/ahkprrrv-ppsgs-19.pdf},
abstract = {Given a set of points in the plane, we want to establish a connected spanning graph between these points, called connection network, that consists of several disjoint layers. Motivated by sensor networks, our goal is that each layer is connected, spanning, and plane. No edge in this connection network is too long in comparison to the length needed to obtain a spanning tree. We consider two different approaches. First we show an almost optimal centralized approach to extract two layers. Then we consider a distributed model in which each point can compute its adjacencies using only information about vertices at most a predefined distance away. We show a constant factor approximation with respect to the length of the longest edge in the graphs. In both cases the obtained layers are plane.},
originalfile = {/geometry/cggg.bib}
}
@article{abhkpsvv-slbnh-19,
author = {O.~Aichholzer and M.~Balko and T.~Hackl and J.~Kyn\v{c}l and
I.~Parada and M.~Scheucher and P.~Valtr and B.~Vogtenhuber},
title = {{{A superlinear lower bound on the number of 5-holes}}},
journal = {Journal of Combinatorial Theory A},
year = 2019,
pages = {1--31},
note = {online},
eprint = {1703.05253},
doi = {10.1016/j.jcta.2020.105236},
url = {https://doi.org/10.1016/j.jcta.2020.105236},
pdf = {/files/publications/geometry/abhkpsvv-slbnh-17.pdf},
abstract = {Let $P$ be a finite set of points in the plane in
\emph{general position}, that is, no three points of
$P$ are on a common line. We say that a set $H$ of
five points from $P$ is a \emph{$5$-hole in~$P$} if
$H$ is the vertex set of a convex $5$-gon containing
no other points of~$P$. For a positive integer $n$,
let $h_5(n)$ be the minimum number of 5-holes among
all sets of $n$ points in the plane in general
position. Despite many efforts in the last 30
years, the best known asymptotic lower and upper
bounds for $h_5(n)$ have been of order $\Omega(n)$
and~$O(n^2)$, respectively. We show that $h_5(n) =
\Omega(n\log^{4/5}{n})$, obtaining the first
superlinear lower bound on $h_5(n)$. The following
structural result, which might be of independent
interest, is a crucial step in the proof of this
lower bound. If a finite set $P$ of points in the
plane in general position is partitioned by a line
$\ell$ into two subsets, each of size at least 5 and
not in convex position, then $\ell$ intersects the
convex hull of some 5-hole in~$P$. The proof of
this result is computer-assisted.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{achkmsv-fdbgo-19,
author = {Oswin Aichholzer and Jean Cardinal and Tony Huynh and Kolja Knauer and Torsten M{\"u}tze and Raphael Steiner and Birgit Vogtenhuber},
title = {{{Flip distances between graph orientations}}},
booktitle = {45th International Workshop on Graph-Theoretic Concepts in Computer Science},
pages = {120--134},
address = {Vall de Nuria, Spain},
series = {Lecture Notes in Computer Science (LNCS)},
volume = {11789},
year = 2019,
eprint = {1902.06103},
archiveprefix = {arXiv},
doi = {10.1007/978-3-030-30786-8_10},
print_isbn = {978-3-030-30785-1},
isbn = {978-3-030-30786-8},
abstract = {Flip graphs are a ubiquitous class of graphs, which encode relations induced on a set of combinatorial objects by elementary, local changes.
A natural computational problem to consider is the flip distance: Given two objects, what is the minimum number of flips needed to transform one into the other?
We consider flip graphs on so-called $\alpha$-orientations of a graph $G$, in which every vertex $v$ has a specified outdegree $\alpha(v)$, and a flip consists of reversing all edges of a directed cycle. We prove that deciding whether the flip distance between two $\alpha$-orientations of a planar graph $G$ is at most 2 is \NP-complete. This also holds in the special case of plane perfect matchings, where flips involve alternating cycles. We also consider the dual question of the flip distance between graph orientations in which every cycle has a specified number of forward edges, and a flip is the reversal of all edges in a minimal directed cut. In general, the problem remains hard, but if we only change sinks into sources, or vice-versa, then the problem can be solved in polynomial time.},
originalfile = {/geometry/cggg.bib}
}
@article{achkmsv-fdbgo-19b,
author = {Oswin Aichholzer and Jean Cardinal and Tony Huynh and Kolja Knauer and Torsten M{\"u}tze and Raphael Steiner and Birgit Vogtenhuber},
title = {{{Flip distances between graph orientations}}},
journal = {Algorithmica},
issn = {0178-4617},
doi = {10.1007/s00453-020-00751-1},
pages = {1--28},
year = 2021,
eprint = {1902.06103},
abstract = {Flip graphs are a ubiquitous class of graphs, which encode relations on a set of combinatorial objects by elementary, local changes.
Skeletons of associahedra, for instance, are the graphs induced by quadrilateral flips in triangulations of a convex polygon.
For some definition of a flip graph, a natural computational problem to consider is the flip distance: Given two objects, what is
the minimum number of flips needed to transform one into the other?
We consider flip graphs on orientations of simple graphs, where flips consist of reversing the direction of some edges.
More precisely, we consider so-called $\alpha$-orientations of a graph $G$, in which every vertex $v$ has a specified outdegree $\alpha(v)$,
and a flip consists of reversing all edges of a directed cycle.
We prove that deciding whether the flip distance between two $\alpha$-orientations of a planar graph $G$ is at most two is \NP-complete.
This also holds in the special case of perfect matchings, where flips involve alternating cycles.
This problem amounts to finding geodesics on the common base polytope of two partition matroids, or, alternatively, on an alcoved polytope.
It therefore provides an interesting example of a flip distance question that is computationally intractable despite having a natural interpretation
as a geodesic on a nicely structured combinatorial polytope.
We also consider the dual question of the flip distance between graph orientations in which every cycle has a specified number of forward edges,
and a flip is the reversal of all edges in a minimal directed cut.
In general, the problem remains hard. However, if we restrict to flips that only change sinks into sources, or vice-versa, then
the problem can be solved in polynomial time. Here we exploit the fact that the flip graph is the cover graph of a distributive lattice.
This generalizes a recent result from Zhang, Qian, and Zhang (Acta. Math. Sin.-English Ser., 2019).},
originalfile = {/geometry/cggg.bib}
}
@article{abhkmppsvvw-mrotg-20,
author = {Oswin Aichholzer and Martin Balko and Michael Hoffmann and Jan Kyn\v{c}l and Wolfgang Mulzer and Irene Parada and Alexander Pilz and Manfred Scheucher and Pavel Valtr and Birgit Vogtenhuber and Emo Welzl},
title = {{{{{Minimal representations of order types by geometric graphs}}}}},
journal = {Journal of Graph Algorithms and Applications},
volume = {24},
number = {4},
pages = {551--572},
doi = {10.7155/jgaa.00545},
note = {special issue of the 27th International Symposium on Graph Drawing and Network Visualization GD$\,$2019},
year = {2020},
abstract = {In order to have a compact visualization of the order type of
a given point set $S$,
we are interested in geometric graphs on $S$ with few edges that unequivocally display
the order type of $S$.
We introduce the concept of \emph{exit edges},
which prevent the order type from changing under continuous motion of vertices.
Exit edges have a natural dual characterization,
which allows us to efficiently compute them and to bound their number.},
originalfile = {/geometry/cggg.bib}
}
@article{aabv-tftm-19,
author = {Oswin Aichholzer and Lukas Andritsch and Karin Baur and Birgit Vogtenhuber},
title = {{{Transformed flips in triangulations and matchings}}},
journal = {submitted},
pages = {1--17},
year = 2019,
eprint = {1907.08758},
archiveprefix = {arXiv},
abstract = {Plane perfect matchings of $2n$ points in convex position are in bijection with triangulations of convex polygons of size $n+2$.
Edge flips are a classic operation to perform local changes both structures have in common.
In this work, we use the explicit bijection from Aichholzer et al. (2018) to determine the effect of an edge flip on the one side of the bijection to the other side,
that is, we show how the two different types of edge flips are related. Moreover, we give an algebraic interpretation of the flip graph of triangulations in terms of
elements of the corresponding Temperley-Lieb algebra.},
originalfile = {/geometry/cggg.bib}
}
@article{hoptv-wscp-19,
title = {{{On weighted sums of numbers of convex polygons in point sets}}},
author = {Clemens Huemer and Deborah Oliveros and Pablo P{\'e}rez-Lantero and Ferran Torra and Birgit Vogtenhuber},
year = {2019},
journal = {submitted},
pages = {1--23},
eprint = {1910.08736},
archiveprefix = {arXiv},
abstract = {Let $S$ be a set of $n$ points in general position in the plane, and let $X_{k,\ell}(S)$ be the number of convex $k$-gons with vertices in $S$ that have
exactly~$\ell$ points of $S$ in their interior. We prove several equalities for the numbers $X_{k,\ell}(S)$. This problem is related to the Erd\H{o}s-Szekeres theorem.
Some of the obtained equations also extend known equations for the numbers of empty convex polygons to polygons with interior points.
Analogous results for higher dimension are shown as well.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{agpvw-sdcss-20,
author = {Oswin Aichholzer and Alfredo Garc\'ia and Irene Parada and Birgit Vogtenhuber and Alexandra Weinberger},
title = {{{Simple Drawings of {$K_{m,n}$} Contain Shooting Stars}}},
booktitle = {Proceedings of the {36th} European Workshop on Computational Geometry (EuroCG$\,$2020)},
pages = {36:1--36:7},
year = 2020,
address = {W\"urzburg, Germany},
pages = {},
url = {http://www1.pub.informatik.uni-wuerzburg.de/eurocg2020/data/uploads/papers/eurocg20_paper_36.pdf},
abstract = {Simple drawings are drawings of graphs in which all edges have at most one common point
(either a common endpoint, or a proper crossing).
It has been an open question whether every simple drawing of a complete bipartite graph
$K_{m,n}$ contains a plane spanning tree as a subdrawing.
We answer this question to the positive by showing that for every simple drawing of $K_{m,n}$
and for every vertex $v$ in that drawing, the drawing contains a \emph{shooting star}
rooted at $v$, that is, a plane spanning tree with all incident edges of $v$.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{akklsvw-rgpsc-20,
author = {Elena Arseneva and Linda Kleist and Boris Klemz and Maarten L\"offler and Andr\'e Schulz and Birgit Vogtenhuber and Alexander Wolff},
title = {{{Representing Graphs by Polygons with Side Contacts in {3D}}}},
booktitle = {Proceedings of the {36th} European Workshop on Computational Geometry (EuroCG$\,$2020)},
year = 2020,
address = {W\"urzburg, Germany},
pages = {},
url = {http://www1.pub.informatik.uni-wuerzburg.de/eurocg2020/data/uploads/papers/eurocg20_paper_53.pdf},
abstract = {A graph has a side-contact representation with polygons if its
vertices can be represented by interior-disjoint polygons such that
two polygons share a common side if and only if the corresponding
vertices are adjacent. In this work we study representations in~3D.
We show that every graph has a side-contact representation with
polygons in~3D, while this is not the case if we additionally
require that the polygons are convex: we show that every
supergraph of $K_5$ and every nonplanar $3$-tree does not admit a
representation with convex polygons. On the other hand, $K_{4,4}$
admits such a representation, and so does every graph obtained from
a complete graph by subdividing each edge once.
Finally, we construct an unbounded family of graphs with average
vertex degree $12-o(1)$ that admit side-contact representations with
convex polygons in 3D. Hence, such graphs can be considerably
denser than planar graphs.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{acdfpvv-sdcoe-20,
author = {O. Aichholzer and L. E. Caraballo and J.M. D\'iaz-B\'a\~nez and R. Fabila-Monroy and I. Parada and I. Ventura and B. Vogtenhuber},
title = {{{Scheduling drones to cover outdoor events}}},
booktitle = {Proceedings of the {36th} European Workshop on Computational Geometry (EuroCG$\,$2020)},
pages = {24:1--24:7},
year = 2020,
address = {W\"urzburg, Germany},
pages = {},
url = {http://www1.pub.informatik.uni-wuerzburg.de/eurocg2020/data/uploads/papers/eurocg20_paper_24.pdf},
abstract = {Task allocation is an important aspect of many multi-robot systems.
In this paper, we consider a new task allocation problem that appears
in multi-robot aerial cinematography. The main goal is to distribute a
set of tasks (shooting actions) among the team members optimizing a
certain objective function.
The tasks are given as sequences of waypoints with associated time
intervals (scenes). We prove that the task allocation problem maximizing
the total filmed time by $k$ aerial robots (drones) can be solved in
polynomial time when the drones do not require battery recharge. We also
consider the problem in which the drones have a limited battery endurance
and must periodically go to a static base station. For this version, we
show how to solve the problem in polynomial time when only one drone is
available.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{akpsvw-ioesdh-20,
author = {Alan Arroyo and
Fabian Klute and
Irene Parada and
Raimund Seidel and
Birgit Vogtenhuber and
Tilo Wiedera},
title = {{{Inserting one edge into a simple drawing is hard}}},
booktitle = {45th International Workshop on Graph-Theoretic Concepts in Computer Science},
__booktitle = {Graph-Theoretic Concepts in Computer Science. WG$\,$2020.},
address = {Leeds, United Kingdom},
year = 2020,
eprint = {1909.07347},
archiveprefix = {arXiv},
doi = {https://doi.org/10.1007/978-3-030-60440-0\_26},
abstract = {A {\em simple drawing} $D(G)$ of a graph $G$ is one where each pair of edges share at most one point: either a common endpoint or a proper crossing. An edge $e$ in the complement of $G$ can be {\em inserted} into $D(G)$ if there exists a simple drawing of $G+e$ extending $D(G)$.
As a result of Levi's Enlargement Lemma, if a drawing is rectilinear (pseudolinear), that is,
the edges can be extended into an arrangement of lines (pseudolines), then any edge in the complement of $G$ can be inserted.
In contrast, we show that it is \NP -complete to decide whether one edge can be inserted into a simple drawing.
This remains true even if we assume that the drawing is pseudocircular, that is,
the edges can be extended to an arrangement of pseudocircles. On the positive side, we show that, given an arrangement of pseudocircles $\mathcal{A}$ and a pseudosegment $\sigma$, it can be decided in polynomial time whether there exists a pseudocircle $\Phi_\sigma$ extending $\sigma$ for which $\mathcal{A}\cup\{\Phi_\sigma\}$ is again an arrangement of pseudocircles.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{abbcfmv-dgs-20,
author = {Oswin Aichholzer and Manuel Borrazzo and Prosenjit Bose and Jean Cardinal and Fabrizio Frati and Pat Morin and Birgit Vogtenhuber},
title = {{{Drawing Graphs as Spanners}}},
booktitle = {45th International Workshop on Graph-Theoretic Concepts in Computer Science. WG$\,$2020.},
__booktitle = {Graph-Theoretic Concepts in Computer Science. WG$\,$2020.},
editor = {Adler, Isolde and M{\"u}ller, Haiko},
address = {Leeds, United Kingdom},
publisher = {Springer International Publishing},
series = {Lecture Notes in Computer Science (LNCS)},
volume = {12301},
pages = {310--324},
year = 2020,
isbn = {978-3-030-60440-0},
doi = {10.1007/978-3-030-60440-0_25},
eprint = {2002.05580},
archiveprefix = {arXiv},
pdf = {/files/publications/geometry/abbcfmv-dgs-20.pdf},
abstract = {We study the problem of embedding graphs in the plane as good geometric spanners. That is, for a graph $G$, the goal is to construct a straight-line drawing $\Gamma$ of $G$ in the plane such that, for any two vertices $u$ and $v$ of $G$, the ratio between the minimum length of any path from $u$ to $v$ and the Euclidean distance between $u$ and $v$ is small. The maximum such ratio, over all pairs of vertices of~$G$, is the \emph{spanning ratio} of $\Gamma$.
First, we show that deciding whether a graph admits a straight-line drawing with spanning ratio~$1$, a proper straight-line drawing with spanning ratio~$1$, and a planar straight-line drawing with spanning ratio~$1$ are NP-complete, $\exists \mathbb R$-complete, and linear-time solvable problems, respectively.
Second, we prove that, for every $\epsilon>0$, every (planar) graph admits a proper (resp.\ planar) straight-line drawing with spanning ratio smaller than~$1+\epsilon$.
Third, we note that our drawings with spanning ratio smaller than~$1+\epsilon$ have large edge-length ratio, that is, the ratio between the lengths of the longest and of the shortest edge is exponential. We show that this is sometimes unavoidable. More generally, we identify having bounded toughness as the criterion that distinguishes graphs that admit straight-line drawings with constant spanning ratio and polynomial edge-length ratio from graphs that do not.},
originalfile = {/geometry/cggg.bib}
}
@article{abbcfmv-dgs-22,
author = {Aichholzer, Oswin and Borrazzo, Manuel and Bose, Prosenjit and Cardinal, Jean and Frati, Fabrizio and Morin, Pat and Vogtenhuber, Birgit},
year = {2022},
month = {06},
pages = {774--795},
volume = {68},
title = {{{Drawing Graphs as Spanners}}},
journal = {Discrete & Computational Geometry},
eprint = {2002.05580},
archiveprefix = {arXiv},
doi = {10.1007/s00454-022-00398-5},
pdf = {/files/publications/geometry/abbcfmv-dgs-20.pdf},
abstract = {We study the problem of embedding graphs in the plane as good geometric spanners. That is, for a graph $G$, the goal is to construct a straight-line drawing $\Gamma$ of $G$ in the plane such that, for any two vertices $u$ and $v$ of $G$, the ratio between the minimum length of any path from $u$ to $v$ and the Euclidean distance between $u$ and $v$ is small. The maximum such ratio, over all pairs of vertices of~$G$, is the \emph{spanning ratio} of $\Gamma$.
First, we show that deciding whether a graph admits a straight-line drawing with spanning ratio~$1$, a proper straight-line drawing with spanning ratio~$1$, and a planar straight-line drawing with spanning ratio~$1$ are NP-complete, $\exists \mathbb R$-complete, and linear-time solvable problems, respectively.
Second, we prove that, for every $\epsilon>0$, every (planar) graph admits a proper (resp.\ planar) straight-line drawing with spanning ratio smaller than~$1+\epsilon$.
Third, we note that our drawings with spanning ratio smaller than~$1+\epsilon$ have large edge-length ratio, that is, the ratio between the lengths of the longest and of the shortest edge is exponential. We show that this is sometimes unavoidable. More generally, we identify having bounded toughness as the criterion that distinguishes graphs that admit straight-line drawings with constant spanning ratio and polynomial edge-length ratio from graphs that do not.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{ckmouv_mmdtfpsmr_20,
author = {Jared Coleman and Evangelos Kranakis and Oscar Morales Ponce and Jaroslav Opatrny and Jorge Urrutia and Birgit Vogtenhuber},
title = {{{Minimizing The Maximum Distance Traveled To Form Patterns With Systems of Mobile Robots}}},
booktitle = {Proc. $32^{nd}$ Annual Canadian Conference on Computational Geometry CCCG 2020},
address = {Saskatoon, Saskatchewan, Canada},
pages = {73--79},
year = {2020},
url = {http://vga.usask.ca/cccg2020/papers/Proceedings.pdf},
eprint = {2006.15664},
archiveprefix = {arXiv},
__url = {https://arxiv.org/abs/2006.15664},
abstract = {In the pattern formation problem, robots in a system must self-coordinate to form a given pattern, regardless of translation, rotation, uniform-scaling, and/or reflection. In other words, a valid final configuration of the system is a formation that is similar to the desired pattern. While there has been no shortage of research in the pattern formation problem under a variety of assumptions, models, and contexts, we consider the additional constraint that the maximum distance traveled among all robots in the system is minimum. Existing work in pattern formation and closely related problems are typically application-specific or not concerned with optimality (but rather feasibility). We show the necessary conditions any optimal solution must satisfy and present a solution for systems of three robots. Our work also led to a surprising result that has applications beyond pattern formation. Namely, a metric for comparing two triangles where a distance of 0 indicates the triangles are similar, and 1 indicates they are fully dissimilar.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{aamppptv-cm2021,
author = {Oswin Aichholzer and Alan Arroyo and Zuzana Mas\'{a}rov\'{a} and Irene Parada and Daniel Perz and Alexander Pilz and Josef Tkadlec and Birgit Vogtenhuber},
title = {{{On Compatible Matchings}}},
booktitle = {WALCOM: Algorithms and Computation},
year = {2021},
publisher = {Springer International Publishing},
adress = {Cham},
pages = {221--233},
editor = {Ryuhei Uehara and Seok-Hee Hong and Subhas C. Nandy},
eprint = {2101.03928},
doi = {10.1007/978-3-030-68211-8_18},
note = {Best Paper Award},
isbn = {978-3-030-68211-8},
abstract = {A matching is compatible to two or more labeled point sets of size $n$ with labels $\{1,\dots,n\}$ if its straight-line drawing on each of these point sets is crossing-free. We study the maximum number of edges in a matching compatible to two or more labeled point sets in general position in the plane. We show that for any two labeled convex sets of $n$ points there exists a compatible matching with $\lfloor \sqrt {2n}\rfloor$ edges. More generally, for any $\ell$ labeled point sets we construct compatible matchings of size $\Omega(n^{1/\ell})$. As a corresponding upper bound, we use probabilistic arguments to show that for any $\ell$ given sets of $n$ points there exists a labeling of each set such that the largest compatible matching has $\mathcal{O}(n^{2/(\ell+1)})$ edges. Finally, we show that $\Theta(\log n)$ copies of any set of $n$ points are necessary and sufficient for the existence of a labeling such that any compatible matching consists only of a single edge.},
originalfile = {/geometry/cggg.bib}
}
@article{aamppptv-cm2022,
author = {{Oswin} {Aichholzer} and {Alan} {Arroyo} and {Zuzana} {Mas\'{a}rov\'{a}} and {Irene} {Parada} and {Daniel} {Perz} and {Alexander} {Pilz} and {Josef} {Tkadlec} and {Birgit} {Vogtenhuber}},
title = {{{On Compatible Matchings}}},
journal = {Journal of Graph Algorithms and Applications},
year = {2022},
volume = {26},
number = {2},
pages = {225--240},
doi = {10.7155/jgaa.00591},
abstract = {A matching is compatible to two or more labeled point sets of size $n$ with labels $\{1,\dots,n\}$ if its straight-line drawing on each of these point sets is crossing-free. We study the maximum number of edges in a matching compatible to two or more labeled point sets in general position in the plane. We show that for any two labeled convex sets of $n$ points there exists a compatible matching with $\lfloor \sqrt {2n}\rfloor$ edges. More generally, for any $\ell$ labeled point sets we construct compatible matchings of size $\Omega(n^{1/\ell})$. As a corresponding upper bound, we use probabilistic arguments to show that for any $\ell$ given sets of $n$ points there exists a labeling of each set such that the largest compatible matching has $\mathcal{O}(n^{2/(\ell+1)})$ edges. Finally, we show that $\Theta(\log n)$ copies of any set of $n$ points are necessary and sufficient for the existence of a labeling such that any compatible matching consists only of a single edge.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{ahoppsvw-pstec20,
author = {Oswin Aichholzer and Michael Hoffmann and Johannes Obenaus and Rosna Paul and Daniel Perz and Nadja Seiferth and Birgit Vogtenhuber and Alexandra Weinberger},
title = {{{Plane Spanning Trees in Edge-Colored Simple Drawings of $K_n$}}},
booktitle = {Graph Drawing and Network Visualization (GD 2020)},
series = {Lecture Notes in Computer Science (LNCS)},
nonote = {28th International Symposium on Graph Drawing and Network Visualization},
doi = {10.1007/978-3-030-68766-3_37},
url = {https://doi.org/10.1007%2F978-3-030-68766-3_37},
publisher = {Springer International Publishing},
pages = {482--489},
eprint = {2008.08827},
archiveprefix = {arXiv},
abstract = {K{\'{a}}rolyi, Pach, and T{\'{o}}th proved that every 2-edge-colored
straight-line drawing of the complete graph contains a monochromatic plane spanning tree.
It is open if this statement generalizes to other classes of drawings, specifically, to \emph{simple drawings} of the complete graph.
These are drawings where edges are represented by Jordan arcs, any two of which intersect at most once.
We present two partial results towards such a generalization. First, we show that the statement holds for cylindrical simple drawings.
(In a \emph{cylindrical} drawing, all vertices are placed on two concentric circles and no edge crosses either circle.)
Second, we introduce a relaxation of the problem in which the graph is $k$-edge-colored,
and the target structure must be \emph{hypochromatic}, that is, avoid (at least) one color class.
In this setting, we show that every $\lceil (n+5)/6\rceil$-edge-colored
monotone simple drawing of $K_n$ contains a hypochromatic plane spanning tree.
(In a \emph{monotone} drawing, every edge is represented as an $x$-monotone curve.)},
year = {2021},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{cfsssv-ccan4cpg-21,
author = {Man-Kwun Chiu and Stefan Felsner and Manfred Scheucher and Felix Schr{\"o}der and Raphael Steiner and Birgit Vogtenhuber},
title = {{{Coloring Circle Arrangements: New 4-Chromatic Planar Graphs}}},
booktitle = {Proceedings of the {37th} European Workshop on Computational Geometry (EuroCG$\,$2021)},
year = 2021,
address = {St. Petersburg, Germany},
pages = {},
url = {http://eurocg21.spbu.ru/wp-content/uploads/2021/04/EuroCG_2021_paper_42.pdf},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{aksv-o4cfpsaub-21,
author = {Oswin Aichholzer and Jan Kyn\v{c}l and Manfred Scheucher and Birgit Vogtenhuber},
title = {{{On 4-Crossing-Families in Point Sets and an Asymptotic Upper Bound}}},
booktitle = {Proceedings of the {37th} European Workshop on Computational Geometry (EuroCG$\,$2021)},
year = 2021,
address = {St. Petersburg, Germany},
pages = {38:1--38:8},
eprint = {2109.10705},
archiveprefix = {arXiv},
archiveprefix = {arXiv},
url = {http://eurocg21.spbu.ru/wp-content/uploads/2021/04/EuroCG_2021_paper_38.pdf},
originalfile = {/geometry/cggg.bib}
}
@article{aksvv-cfps-22,
title = {{{On crossing-families in planar point sets}}},
journal = {Computational Geometry},
volume = {107},
pages = {101-899},
year = {2022},
issn = {0925-7721},
eprint = {2109.10705},
archiveprefix = {arXiv},
doi = {https://doi.org/10.1016/j.comgeo.2022.101899},
url = {https://www.sciencedirect.com/science/article/pii/S0925772122000426},
author = {Oswin Aichholzer and Jan Kyn\v{c}l and Manfred Scheucher and Birgit Vogtenhuber and Pavel Valtr},
keywords = {Crossing family, Point set, Order type, Geometric thrackle},
abstract = {A k-crossing family in a point set S in general position is a set of k segments spanned by points of S such that all k segments mutually cross. In this short note we present two statements on crossing families which are based on sets of small cardinality: (1) Any set of at least 15 points contains a crossing family of size 4. (2) There are sets of n points which do not contain a crossing family of size larger than 8⌈n41⌉. Both results improve the previously best known bounds.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{akklsvw-agps-21,
author = {Arseneva, Elena and Kleist, Linda and Klemz, Boris and L\"{o}ffler, Maarten and Schulz, Andr\'{e} and Vogtenhuber, Birgit and Wolff, Alexander},
title = {{{{Adjacency Graphs of Polyhedral Surfaces}}}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {11:1--11:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
isbn = {978-3-95977-184-9},
issn = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
url = {https://drops.dagstuhl.de/opus/volltexte/2021/13810},
urn = {urn:nbn:de:0030-drops-138107},
doi = {10.4230/LIPIcs.SoCG.2021.11},
annote = {Keywords: polyhedral complexes, realizability, contact representation},
abstract = {We study whether a given graph can be realized as an
adjacency graph of the polygonal cells of a polyhedral surface
in~$\mathbb{R}^3$.
We show that every graph is realizable as a polyhedral surface with
arbitrary polygonal cells, and that this is not true if we require the cells
to be convex.
In particular, if the given graph contains $K_5$, $K_{5,81}$, or
any nonplanar $3$-tree as a subgraph, no such realization exists.
On the other hand, all planar graphs, $K_{4,4}$, and $K_{3,5}$ can
be realized with convex cells.
The same holds for any subdivision of any graph where each edge
is subdivided at least once, and, by a result from McMullen et
al.~(1983), for any hypercube.
Our results have implications on the maximum density of graphs
describing polyhedral surfaces with convex cells:
The realizability of hypercubes shows that the maximum number of
edges over all realizable $n$-vertex graphs is in $\Omega(n \log n)$.
From the non-realizability of $K_{5,81}$, we obtain that
any realizable $n$-vertex graph has $\bigO(n^{9/5})$ edges.
As such, these graphs can be considerably denser than planar graphs, but not arbitrarily dense.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{agtvw-pmsdcg-21,
author = {Oswin Aichholzer and Alfredo Garc\'{\i}a and Javier Tejel and Birgit Vogtenhuber and Alexandra Weinberger},
title = {{{Plane Matchings in Simple Drawings of Complete Graphs}}},
booktitle = {Proceedings of the Computational Geometry: Young Researchers Forum},
year = {2021},
pages = {6-10},
url = {https://cse.buffalo.edu/socg21/files/YRF-Booklet.pdf#page=6},
abstract = {Simple drawings are drawings of graphs in which the edges are Jordan arcs and each pair of edges shares at most one point (a proper crossing or a common endpoint). We show that every simple drawing of the complete graph with~$n$ vertices contains~$\Omega(n^{\frac{1}{2}})$ pairwise disjoint edges. This improves the currently known best lower bound $\Omega(n^{\frac{1}{2}-\varepsilon})$ for any $\varepsilon>0$ by Ruiz-Vargas.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{afkpppsv-pmwc-21,
author = {Oswin Aichholzer and Ruy Fabila-Monroy and Philipp Kindermann and Irene Parada and Rosna Paul and Daniel Perz and Patrick Schnider and Birgit Vogtenhuber},
title = {{{Perfect Matchings with Crossings}}},
booktitle = {Proceedings of the Computational Geometry: Young Researchers Forum},
year = {2021},
pages = {24-27},
url = {https://cse.buffalo.edu/socg21/files/YRF-Booklet.pdf#page=24},
abstract = {In this paper, we analyze the number of straight-line perfect matchings with $k$ crossings on point sets of size $n$ = $2m$ in general position. We show that for every $k\leq 5n/8-\Theta(1)$, every $n$-point set admits a perfect matching with exactly $k$ crossings and that there exist $n$-point sets where every perfect matching has fewer than $5n^2/72$ crossings. We also study the number of perfect matchings with at most $k$ crossings. Finally we show that convex point sets %in convex position maximize the number of perfect matchings with $n/2 \choose 2$ crossings and ${n/2 \choose 2}\!-\!1$ crossings.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{agtvw-pmsdcg-21b,
author = {Oswin Aichholzer and Alfredo Garc\'{\i}a and Javier Tejel and Birgit Vogtenhuber and Alexandra Weinberger},
title = {{{Plane paths in simple drawings of complete graphs}}},
booktitle = {Proc. XIX Encuentros de Geometr\'{\i}a Computacional},
year = {2021},
pages = {4},
abstract = {Simple drawings are drawings of graphs in the plane such that vertices are distinct points in the plane, edges are Jordan arcs connecting their endpoints, and edges intersect at most once either in a proper crossing or in a shared endpoint. It is conjectured that every simple drawing of the complete graph with $n$ vertices, $K_n$, contains a plane Hamiltonian cycle, and consequently a plane Hamiltonian path.
However, to the best of our knowledge, $\Omega((\log n)^{1/6})$ is currently the best known lower bound for the length of a plane path contained in any simple drawing of $K_n$. We improve this bound to $\Omega(\log n / (\log \log n) )$.},
url = {https://quantum-explore.com/wp-content/uploads/2021/06/Actas_egc21.pdf#page=11},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{ghkpv-coesd-21egc,
author = {Robert Ganian and Thekla Hamm and Fabian Klute and Irene Parada and Birgit Vogtenhuber},
title = {{{Crossing-optimal extension of simple drawings}}},
booktitle = {Proc. XIX Encuentros de Geometr\'{\i}a Computacional},
year = {2021},
pages = {5},
url = {https://quantum-explore.com/wp-content/uploads/2021/06/Actas_egc21.pdf#page=12},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{fhpv-nslet-21,
author = {Ruy Fabila-Monroy and Carlos Hidalgo-Toscano and Daniel Perz and Birgit Vogtenhuber},
title = {{{No selection lemma for empty triangles}}},
booktitle = {Proc. XIX Encuentros de Geometr\'{\i}a Computacional},
year = {2021},
pages = {36},
url = {https://quantum-explore.com/wp-content/uploads/2021/06/Actas_egc21.pdf#page=43},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{ghkpv-coesd-21icalp,
author = {Robert Ganian and Thekla Hamm and Fabian Klute and Irene Parada and Birgit Vogtenhuber},
title = {{{{Crossing-Optimal Extension of Simple Drawings}}}},
booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
pages = {72:1--72:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
isbn = {978-3-95977-195-5},
issn = {1868-8969},
year = {2021},
volume = {198},
editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
url = {https://drops.dagstuhl.de/opus/volltexte/2021/14141},
urn = {urn:nbn:de:0030-drops-141412},
doi = {10.4230/LIPIcs.ICALP.2021.72},
annote = {Keywords: Simple drawings, Extension problems, Crossing minimization, FPT-algorithms},
abstract = {In extension problems of partial graph drawings one is given an incomplete drawing of an input graph G and is asked to complete the drawing while maintaining certain properties. A prominent area where such problems arise is that of crossing minimization. For plane drawings and various relaxations of these, there is a number of tractability as well as lower-bound results exploring the computational complexity of crossing-sensitive drawing extension problems. In contrast, comparatively few results are known on extension problems for the fundamental and broad class of simple drawings, that is, drawings in which each pair of edges intersects in at most one point. In fact, the extension problem of simple drawings has only recently been shown to be NP-hard even for inserting a single edge.
In this paper we present tractability results for the crossing-sensitive extension problem of simple drawings. In particular, we show that the problem of inserting edges into a simple drawing is fixed-parameter tractable when parameterized by the number of edges to insert and an upper bound on newly created crossings. Using the same proof techniques, we are also able to answer several closely related variants of this problem, among others the extension problem for k-plane drawings. Moreover, using a different approach, we provide a single-exponential fixed-parameter algorithm for the case in which we are only trying to insert a single edge into the drawing.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{fhpv-nslet-21b,
author = {Fabila-Monroy, Ruy and Hidalgo-Toscano, Carlos and Perz, Daniel and Vogtenhuber, Birgit},
editor = {Ne{\v{s}}et{\v{r}}il, Jaroslav and Perarnau, Guillem and Ru{\'e}, Juanjo and Serra, Oriol},
title = {{{No Selection Lemma for Empty Triangles}}},
booktitle = {Extended Abstracts EuroComb 2021},
year = {2021},
publisher = {Springer International Publishing},
address = {Cham},
pages = {720--725},
abstract = {In this paper we show that for any integer $n$ and real number $0\leq \alpha \leq 1$ there exists a point set of size $n$ with $\Theta(n^{3-\alpha})$ empty triangles such that any point of the plane is in
$O(n^{3-2\alpha})$ empty triangles.},
isbn = {978-3-030-83823-2},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{cfsssv-ccan4cpg-21b,
author = {Chiu, Man-Kwun and Felsner, Stefan and Scheucher, Manfred and Schr{\"o}der, Felix and Steiner, Raphael and Vogtenhuber, Birgit},
editor = {Ne{\v{s}}et{\v{r}}il, Jaroslav and Perarnau, Guillem and Ru{\'e}, Juanjo and Serra, Oriol},
title = {{{Coloring Circle Arrangements: New 4-Chromatic Planar Graphs}}},
booktitle = {Extended Abstracts EuroComb 2021},
year = {2021},
publisher = {Springer International Publishing},
address = {Cham},
pages = {84--91},
abstract = {Felsner, Hurtado, Noy and Streinu (2000) conjectured that arrangement graphs of simple great-circle arrangements have chromatic number at most 3. This paper is motivated by the conjecture.
We show that the conjecture holds in the special case when the arrangement
is \emph{$\triangle$-saturated}, i.e., arrangements where one color class of
the 2-coloring of faces consists of triangles only. Moreover, we extend
$\triangle$-saturated arrangements with certain properties to a family of
arrangements which are 4-chromatic. The construction has similarities with Koester's
(1985) crowning construction.
We also investigate fractional colorings. We show that every arrangement
$\mathcal{A}$ of pairwise intersecting pseudocircles is ``close'' to being
$3$-colorable; more precisely $\chi_f(\mathcal{A}) \le 3+O(\frac{1}{n})$
where $n$ is the number of pseudocircles. Furthermore, we construct an infinite
family of $4$-edge-critical $4$-regular planar graphs which are fractionally
$3$-colorable. This disproves the conjecture of Gimbel, K{\"u}ndgen, Li and
Thomassen (2019) that every $4$-chromatic planar graph has fractional
chromatic number strictly greater than~$3$.},
isbn = {978-3-030-83823-2},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{allmopppvw-d-21,
author = {Aichholzer, Oswin and L{\"o}ffler, Maarten and Lynch, Jayson and Mas{\'a}rov{\'a}, Zuzana and Orthaber, Joachim and Parada, Irene and Paul, Rosna and Perz, Daniel and Vogtenhuber, Birgit and Weinberger, Alexandra},
title = {{{Dominect: A Simple yet Deep 2-Player Board Game}}},
year = {2021},
pages = {112--113},
booktitle = {23rd Thailand-Japan Conference on Discrete and Computational Geometry, Graphs, and Games (TJCDCGGG 2020+1)},
url = {http://www.math.science.cmu.ac.th/tjcdcggg/},
abstract = {In this work we introduce the perfect information 2-player game \emph{Dominect}, which has recently been invented by two of the authors. Despite being a game with quite simple rules, Dominect reveals a high depth of complexity. We report on first results concerning the development of winning strategies, as well as a PSPACE-hardness result for deciding whether a given game position is a winning position.},
originalfile = {/geometry/cggg.bib}
}
@article{FLORESPENALOZA2021112406,
title = {{{Rainbow polygons for colored point sets in the plane}}},
journal = {Discrete Mathematics},
volume = {344},
number = {7},
pages = {112406},
year = {2021},
issn = {0012-365X},
doi = {https://doi.org/10.1016/j.disc.2021.112406},
url = {https://www.sciencedirect.com/science/article/pii/S0012365X21001199},
author = {David Flores-Pe{\~n}aloza and Mikio Kano and Leonardo Mart{\'i}nez-Sandoval and David Orden and Javier Tejel and Csaba D. T{\'o}th and Jorge Urrutia and Birgit Vogtenhuber},
keywords = {Colored point set, Enclosing simple polygon, Particular cases, General bounds},
abstract = {Given a colored point set in the plane, a \emph{perfect rainbow polygon} is a simple polygon that \emph{contains} exactly one point of each color, either in its interior or on its boundary. Let $\operatorname{rb-index}(S)$ denote the smallest size of a perfect rainbow polygon for a colored point set $S$, and let $\operatorname{rb-index}(k)$ be the maximum of $\operatorname{rb-index}(S)$ over all $k$-colored point sets in general position; that is, every $k$-colored point set $S$ has a perfect rainbow polygon with at most $\operatorname{rb-index}(k)$ vertices. In this paper, we determine the values of $\operatorname{rb-index}(k)$ up to $k=7$, which is the first case where $\operatorname{rb-index}(k)\neq k$, and we prove that for $k\ge 5$,
\[
\frac{40\lfloor (k-1)/2 \rfloor -8}{19}
\leq\operatorname{rb-index}(k)\leq 10 \bigg\lfloor\frac{k}{7}\bigg\rfloor + 11.
\]
Furthermore, for a $k$-colored set of $n$ points in the plane in general position, a perfect rainbow polygon with at most $10 \lfloor\frac{k}{7}\rfloor + 11$
vertices can be computed in $O(n\log n)$ time.},
originalfile = {/geometry/cggg.bib}
}
@article{bckmrrssvw-rpd20,
title = {{{Routing in polygonal domains}}},
journal = {Computational Geometry},
volume = {87},
pages = {101593},
year = {2020},
note = {Special Issue on the 33rd European Workshop on Computational Geometry},
issn = {0925-7721},
doi = {https://doi.org/10.1016/j.comgeo.2019.101593},
url = {https://www.sciencedirect.com/science/article/pii/S0925772119301348},
author = {Bahareh Banyassady and Man-Kwun Chiu and Matias Korman and Wolfgang Mulzer and Andr{\'e} {van Renssen} and Marcel Roeloffzen and Paul Seiferth and Yannik Stein and Birgit Vogtenhuber and Max Willert},
keywords = {Routing scheme, Polygonal domain},
abstract = {We consider the problem of routing a data packet through the visibility graph of a polygonal domain $P$ with $n$ vertices and $h$ holes.
We may preprocess $P$ to obtain a label and a routing table for each vertex of $P$.
Then, we must be able to route a data packet between any two vertices $p$ and $q$ of $P$,
where each step must use only the label of the target node $q$ and the routing table of the current node.
For any fixed $\varepsilon>0$, we present a routing scheme that always achieves a routing path whose length
exceeds the shortest path by a factor of at most $1+\varepsilon$.
The labels have $O(\log n)$ bits, and the routing tables are of size $O((\varepsilon-1+h)\log n)$.
The preprocessing time is $O(n^2 \log n)$. It can be improved to $O(n^2)$ for simple polygons.},
originalfile = {/geometry/cggg.bib}
}
@article{aichholzer2021edge,
title = {{{Edge Partitions of Complete Geometric Graphs (Part 2)}}},
author = {Oswin Aichholzer and Johannes Obenaus and Joachim Orthaber and Rosna Paul and Patrick Schnider and Raphael Steiner and Tim Taubner and Birgit Vogtenhuber},
year = {2021},
eprint = {2112.08456},
archiveprefix = {arXiv},
abstract = {Recently, the second and third author showed that complete geometric graphs on $2n$ vertices in general cannot be partitioned into $n$ plane spanning trees. Building up on this work, in this paper, we initiate the study of partitioning into beyond planar subgraphs, namely into $k$-planar and $k$-quasi-planar subgraphs and obtain first bounds on the number of subgraphs required in this setting.},
primaryclass = {math.CO},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{achhmv-gtcbg-22,
author = {Oswin Aichholzer and Man-Kwun Chiu and Hung P. Hoang and Michael Hoffmann and
Yannic Maus and Birgit Vogtenhuber and Alexandra Weinberger},
title = {{{Gioan{'}s Theorem for complete bipartite graphs}}},
booktitle = {Proc. $38^{th}$ European Workshop on Computational Geometry (EuroCG 2022)},
pages = {31:1--31:6},
year = 2022,
address = {Perugia, Italy},
pdf = {https://eurocg2022.unipg.it/booklet/EuroCG2022-Booklet.pdf#page=226},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{ahlppsv-bdte-22,
author = {Oswin Aichholzer and Thomas Hackl and Maarten L{\"o}ffler and Alexander
Pilz and Irene Parada and Manfred Scheucher and Birgit Vogtenhuber},
title = {{{Blocking Delaunay Triangulations from Exterior}}},
booktitle = {Proc. $38^{th}$ European Workshop on Computational Geometry (EuroCG 2022)},
pages = {9:1--9:7},
year = 2022,
address = {Perugia, Italy},
eprint = {2210.12015},
archiveprefix = {arXiv},
pdf = {https://eurocg2022.unipg.it/booklet/EuroCG2022-Booklet.pdf#page=65},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{aklmmopv-fpsp-22,
author = {Oswin Aichholzer and Kristin Knorr and Maarten L{\"o}ffler and Zuzana Mas{\'{a}}rov{\'{a}} and Wolfgang Mulzer and Johannes Obenaus and Rosna Paul and Birgit Vogtenhuber},
title = {{{Flipping Plane Spanning Paths}}},
booktitle = {Proc. $38^{th}$ European Workshop on Computational Geometry (EuroCG 2022)},
pages = {66:1--66:7},
year = 2022,
address = {Perugia, Italy},
eprint = {2202.10831},
archiveprefix = {arXiv},
pdf = {https://eurocg2022.unipg.it/booklet/EuroCG2022-Booklet.pdf#page=478},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{bfv-idwa-22,
author = {Daniel Bertschinger and Henry F{\"o}rster, and Birgit Vogtenhuber},
title = {{{Intersections of Double-Wedge Arrangements}}},
booktitle = {Proc. $38^{th}$ European Workshop on Computational Geometry (EuroCG 2022)},
pages = {58:1--58:6},
year = 2022,
address = {Perugia, Italy},
pdf = {https://eurocg2022.unipg.it/booklet/EuroCG2022-Booklet.pdf#page=418},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{agtvw-twfpssdcg-22,
author = {Oswin Aichholzer and Alfredo Garc\'{\i}a and Javier Tejel and Birgit Vogtenhuber and Alexandra Weinberger},
title = {{{{Twisted Ways to Find Plane Structures in Simple Drawings of Complete Graphs}}}},
booktitle = {38th International Symposium on Computational Geometry
(SoCG 2022)},
pages = {5:1--5:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
isbn = {978-3-95977-227-3},
issn = {1868-8969},
year = {2022},
volume = {224},
editor = {Goaoc, Xavier and Kerber, Michael},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
eprint = {2203.06143},
archiveprefix = {arXiv},
url = {https://drops.dagstuhl.de/opus/volltexte/2022/16013},
doi = {10.4230/LIPIcs.SoCG.2022.5},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{afkpppsv-pmc-22,
author = {Aichholzer, Oswin and Fabila-Monroy, Ruy and Kindermann, Philipp and Parada, Irene and Paul, Rosna and Perz, Daniel and Schnider, Patrick and Vogtenhuber, Birgit},
title = {{{Perfect Matchings with Crossings}}},
year = {2022},
isbn = {978-3-031-06677-1},
publisher = {Springer-Verlag},
address = {Berlin, Heidelberg},
doi = {10.1007/978-3-031-06678-8_4},
booktitle = {Combinatorial Algorithms: 33rd International Workshop, IWOCA 2022, Trier, Germany, June 7--9, 2022, Proceedings},
pages = {46--59},
numpages = {14},
keywords = {Combinatorial geometry, Order types, Perfect matchings, Crossings},
location = {Trier, Germany},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{akmeoprvw-cstsd-23,
author = {Aichholzer, Oswin
and Knorr, Kristin
and Mulzer, Wolfgang
and El Maalouly, Nicolas
and Obenaus, Johannes
and Paul, Rosna
and M. Reddy, Meghana
and Vogtenhuber, Birgit
and Weinberger, Alexandra},
editor = {Angelini, Patrizio and von Hanxleden, Reinhard},
title = {{{Compatible Spanning Trees in Simple Drawings of {$K_{n}$}}}},
booktitle = {Graph Drawing and Network Visualization},
year = {2023},
publisher = {Springer International Publishing},
address = {Cham},
pages = {16--24},
isbn = {978-3-031-22203-0},
doi = {10.1007/978-3-031-22203-0_2},
eprint = {2208.11875},
archiveprefix = {arXiv},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{gtvw-etgtd-23,
author = {Garc{\'i}a, Alfredo
and Tejel, Javier
and Vogtenhuber, Birgit
and Weinberger, Alexandra},
editor = {Angelini, Patrizio and von Hanxleden, Reinhard},
title = {{{Empty Triangles in Generalized Twisted Drawings of {$K_{n}$}}}},
booktitle = {Graph Drawing and Network Visualization},
year = {2023},
publisher = {Springer International Publishing},
address = {Cham},
pages = {40--48},
isbn = {978-3-031-22203-0},
doi = {10.1007/978-3-031-22203-0_4},
eprint = {2208.05819},
archiveprefix = {arXiv},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{agpvw-sssd-23,
author = {Aichholzer, Oswin
and Garc{\'i}a, Alfredo
and Parada, Irene
and Vogtenhuber, Birgit
and Weinberger, Alexandra},
editor = {Angelini, Patrizio and von Hanxleden, Reinhard},
title = {{{Shooting Stars in Simple Drawings of {$K_{m,n}$}}}},
booktitle = {Graph Drawing and Network Visualization},
year = {2023},
publisher = {Springer International Publishing},
address = {Cham},
pages = {49--57},
isbn = {978-3-031-22203-0},
doi = {10.1007/978-3-031-22203-0_5},
eprint = {2209.01190},
archiveprefix = {arXiv},
originalfile = {/geometry/cggg.bib}
}
@article{akoppvv-gwlta-23,
title = {{{Graphs with large total angular resolution}}},
journal = {Theoretical Computer Science},
volume = {943},
pages = {73-88},
year = {2023},
issn = {0304-3975},
eprint = {1908.06504},
archiveprefix = {arXiv},
doi = {https://doi.org/10.1016/j.tcs.2022.12.010},
url = {https://www.sciencedirect.com/science/article/pii/S0304397522007320},
author = {Oswin Aichholzer and Matias Korman and Yoshio Okamoto and Irene Parada and Daniel Perz and Andr\'e {van Renssen} and Birgit Vogtenhuber},
keywords = {Graph drawing, Total angular resolution, Angular resolution, Crossing resolution, NP-hardness},
abstract = {The total angular resolution of a straight-line drawing is the minimum angle between two edges of the drawing. It combines two properties contributing to the readability of a drawing: the angular resolution, which is the minimum angle between incident edges, and the crossing resolution, which is the minimum angle between crossing edges. We consider the total angular resolution of a graph, which is the maximum total angular resolution of a straight-line drawing of this graph. We prove tight bounds for the number of edges for graphs for some values of the total angular resolution up to a finite number of well specified exceptions of constant size. In addition, we show that deciding whether a graph has total angular resolution at least 60∘ is NP-hard. Further we present some special graphs and their total angular resolution.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{aopptv-dcvgc-22,
author = {Aichholzer, Oswin and Obmann, Julia and Pat{\'a}k, Pavel and Perz, Daniel and Tkadlec, Josef and Vogtenhuber, Birgit},
editor = {Bekos, Michael A. and Kaufmann, Michael},
title = {{{Disjoint Compatibility via Graph Classes}}},
booktitle = {Graph-Theoretic Concepts in Computer Science. WG 2022.},
year = {2022},
publisher = {Springer International Publishing},
address = {Cham},
pages = {16--28},
doi = {https://doi.org/10.1007/978-3-031-15914-5_2},
series = {Lecture Notes in Computer Science (LNCS)},
volume = {13453},
abstract = {Two plane drawings of graphs on the same set of points are called disjoint compatible if their union is plane and they do not have an edge in common.
Let $S$ be a convex point set of $2n \geq 10$ points and let $\mathcal{H}$ be a family of plane drawings on $S$.
Two plane perfect matchings $M_1$ and $M_2$ on $S$ (which do not need to be disjoint nor compatible) are \emph{disjoint $\mathcal{H}$-compatible} if there exists a drawing in $\mathcal{H}$ which is disjoint compatible to both $M_1$ and $M_2$.
In this work, we consider the graph which has all plane perfect matchings as vertices and where two vertices are connected by an edge if the matchings are disjoint $\mathcal{H}$-compatible.
We study the diameter of this graph when $\mathcal{H}$ is the family of all plane spanning trees, caterpillars or paths.
We show that in the first two cases the graph is connected with constant and linear diameter, respectively, while in the third case it is disconnected.},
isbn = {978-3-031-15914-5},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{aov-2023-tcfhcsdcg,
title = {{{Towards Crossing-Free Hamiltonian Cycles in Simple Drawings of Complete Graphs}}},
author = {Aichholzer, Oswin and Orthaber, Joachim and Vogtenhuber, Birgit},
booktitle = {Proceedings of the 39th European Workshop on Computational Geometry (EuroCG 2023)},
pages = {33:1--33:7},
year = {2023},
url = {https://dccg.upc.edu/eurocg23/wp-content/uploads/2023/03/Session-5B-Talk-2.pdf},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{bpmc-afpsv-23,
title = {{{Bichromatic Perfect Matchings with Crossings}}},
author = {Oswin Aichholzer and Stefan Felsner and Rosna Paul and Manfred Scheucher and Birgit Vogtenhuber},
booktitle = {Proceedings of the 39th European Workshop on Computational Geometry (EuroCG 2023)},
pages = {28:1--28:7},
year = {2023},
url = {https://dccg.upc.edu/eurocg23/wp-content/uploads/2023/05/Booklet_EuroCG2023.pdf},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{akmopv-fpsp-23,
author = {Aichholzer, Oswin and Knorr, Kristin and Mulzer, Wolfgang and Obenaus, Johannes and Paul, Rosna and Vogtenhuber, Birgit},
year = {2023},
month = {03},
pages = {49-60},
title = {{{Flipping Plane Spanning Paths}}},
isbn = {978-3-031-27050-5},
doi = {10.1007/978-3-031-27051-2_5},
editor = {Lin, Chun-Cheng and Lin, Bertrand M. T. and Liotta, Giuseppe},
booktitle = {WALCOM: Algorithms and Computation},
publisher = {Springer Nature Switzerland},
address = {Cham},
abstract = {Let S be a planar point set in general position, and let {\$}{\$}{\backslash}mathcal {\{}P{\}}(S){\$}{\$}be the set of all plane straight-line paths with vertex set S. A flip on a path {\$}{\$}P {\backslash}in {\backslash}mathcal {\{}P{\}}(S){\$}{\$}is the operation of replacing an edge e of P with another edge f on S to obtain a new valid path from {\$}{\$}{\backslash}mathcal {\{}P{\}}(S){\$}{\$}. It is a long-standing open question whether for every given point set S, every path from {\$}{\$}{\backslash}mathcal {\{}P{\}}(S){\$}{\$}can be transformed into any other path from {\$}{\$}{\backslash}mathcal {\{}P{\}}(S){\$}{\$}by a sequence of flips. To achieve a better understanding of this question, we show that it is sufficient to prove the statement for plane spanning paths whose first edge is fixed. Furthermore, we provide positive answers for special classes of point sets, namely, for wheel sets and generalized double circles (which include, e.g., double chains and double circles).},
eprint = {2202.10831},
archiveprefix = {arXiv},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{aichholzer_et_al:LIPIcs.SoCG.2023.6,
author = {Aichholzer, Oswin and Chiu, Man-Kwun and Hoang, Hung P. and Hoffmann, Michael and Kyn\v{c}l, Jan and Maus, Yannic and Vogtenhuber, Birgit and Weinberger, Alexandra},
title = {{{{Drawings of Complete Multipartite Graphs up to Triangle Flips}}}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {6:1--6:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
isbn = {978-3-95977-273-0},
issn = {1868-8969},
year = {2023},
volume = {258},
editor = {Chambers, Erin W. and Gudmundsson, Joachim},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
url = {https://drops.dagstuhl.de/opus/volltexte/2023/17856},
urn = {urn:nbn:de:0030-drops-178563},
doi = {10.4230/LIPIcs.SoCG.2023.6},
annote = {Keywords: Simple drawings, simple topological graphs, complete graphs, multipartite graphs, k-partite graphs, bipartite graphs, Gioan’s Theorem, triangle flips, Reidemeister moves},
originalfile = {/geometry/cggg.bib}
}
@article{twisted,
author = {Aichholzer, Oswin and Garc{\'i}a, Alfredo and Tejel, Javier and Vogtenhuber, Birgit and Weinberger, Alexandra},
year = {2024},
title = {{{Twisted Ways to Find Plane Structures in Simple Drawings of Complete Graphs}}},
journal = {Discrete \& Computational Geometry},
pages = {40-66},
volume = {71},
abstract = {Simple drawings are drawings of graphs in which the edges are Jordan arcs and each pair of edges share at most one point (a proper crossing or a common endpoint). A simple drawing is c-monotone if there is a point O such that each ray emanating from O crosses each edge of the drawing at most once. We introduce a special kind of c-monotone drawings that we call generalized twisted drawings. A c-monotone drawing is generalized twisted if there is a ray emanating from O that crosses all the edges of the drawing. Via this class of drawings, we show that every simple drawing of the complete graph with n vertices contains $$\Omega (n^{\frac{1}{2}})$$pairwise disjoint edges and a plane cycle (and hence path) of length $$\Omega (\frac{\log n }{\log \log n})$$. Both results improve over best previously published lower bounds. On the way we show several structural results and properties of generalized twisted and c-monotone drawings, some of which we believe to be of independent interest. For example, we show that a drawing D is c-monotone if there exists a point O such that no edge of D is crossed more than once by any ray that emanates from O and passes through a vertex of D.},
doi = {10.1007/s00454-023-00610-0},
originalfile = {/geometry/cggg.bib}
}
@article{Aichholzer_Orthaber_Vogtenhuber_2024,
title = {{{Towards Crossing-Free Hamiltonian Cycles in Simple Drawings of Complete Graphs}}},
volume = {3},
url = {https://www.cgt-journal.org/index.php/cgt/article/view/47},
doi = {10.57717/cgt.v3i2.47},
abstract = {It is a longstanding conjecture that every simple drawing of a complete graph on $n\geq 3$ vertices contains a crossing-free Hamiltonian cycle. We strengthen this conjecture to \enquote{there exists a crossing-free Hamiltonian path between each pair of vertices} and show that this stronger conjecture holds for several classes of simple drawings, including strongly c-monotone drawings and cylindrical drawings. As a second main contribution, we give an overview on different classes of simple drawings and investigate inclusion relations between them up to weak isomorphism.},
number = {2},
journal = {Computing in Geometry and Topology},
author = {Aichholzer, Oswin and Orthaber, Joachim and Vogtenhuber, Birgit},
year = {2024},
month = {Jan.},
pages = {5:1--5:30},
originalfile = {/geometry/cggg.bib}
}
@article{afkpppsv-pmwc-24,
author = {Aichholzer, Oswin and Fabila-Monroy, Ruy and Kindermann, Philipp and Parada, Irene and Paul, Rosna and Perz, Daniel and Schnider, Patrick and Vogtenhuber, Birgit},
title = {{{Perfect Matchings with Crossings}}},
journal = {Algorithmica},
volume = {86},
pages = {697--716},
year = {2024},
abstract = {For sets of n points, n even, in general position in the plane, we consider straight-line drawings of perfect matchings on them. It is well known that such sets admit at least $$C_{n/2}$$different plane perfect matchings, where $$C_{n/2}$$is the n/2-th Catalan number. Generalizing this result we are interested in the number of drawings of perfect matchings which have k crossings. We show the following results. (1) For every $$k\le \frac{1}{64}n^2-\frac{35}{32}n\sqrt{n}+\frac{1225}{64}n$$, any set with n points, n sufficiently large, admits a perfect matching with exactly k crossings. (2) There exist sets of n points where every perfect matching has at most $$\frac{5}{72}n^2-\frac{n}{4}$$crossings. (3) The number of perfect matchings with at most k crossings is superexponential in n if k is superlinear in n. (4) Point sets in convex position minimize the number of perfect matchings with at most k crossings for $$k=0,1,2$$, and maximize the number of perfect matchings with $$\left( {\begin{array}{c}n/2\\ 2\end{array}}\right) $$crossings and with $${\left( {\begin{array}{c}n/2\\ 2\end{array}}\right) }\!-\!1$$crossings.},
doi = {10.1007/s00453-023-01147-7},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{avw-dtidcmg-23,
author = {Aichholzer, Oswin and Vogtenhuber, Birgit and Weinberger, Alexandra},
editor = {Bekos, Michael A. and Chimani, Markus},
title = {{"Different Types of Isomorphisms of Drawings of Complete Multipartite Graphs"}},
booktitle = {Graph Drawing and Network Visualization},
series = {Lecture Notes in Computer Science (LNCS)},
volume = {14466},
year = {2023},
publisher = {Springer Nature Switzerland},
address = {Cham},
pages = {34--50},
doi = {10.1007/978-3-031-49275-4_3},
eprint = {2308.10735},
archiveprefix = {arXiv},
abstract = {Simple drawings are drawings of graphs in which any two edges intersect at most once (either at a common endpoint or a proper crossing), and no edge intersects itself. We analyze several characteristics of simple drawings of complete multipartite graphs: which pairs of edges cross, in which order they cross, and the cyclic order around vertices and crossings, respectively. We consider all possible combinations of how two drawings can share some characteristics and determine which other characteristics they imply and which they do not imply. Our main results are that for simple drawings of complete multipartite graphs, the orders in which edges cross determine all other considered characteristics. Further, if all partition classes have at least three vertices, then the pairs of edges that cross determine the rotation system and the rotation around the crossings determine the extended rotation system. We also show that most other implications -- including the ones that hold for complete graphs -- do not hold for complete multipartite graphs. Using this analysis, we establish which types of isomorphisms are meaningful for simple drawings of complete multipartite graphs.},
isbn = {978-3-031-49275-4},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{afpsv-bpmc-23,
author = {Aichholzer, Oswin and Felsner, Stefan and Paul, Rosna and Scheucher, Manfred and Vogtenhuber, Birgit},
editor = {Bekos, Michael A. and Chimani, Markus},
title = {{"Bichromatic Perfect Matchings with Crossings"}},
booktitle = {Graph Drawing and Network Visualization},
series = {Lecture Notes in Computer Science (LNCS)},
volume = {14465},
year = {2023},
publisher = {Springer Nature Switzerland},
address = {Cham},
pages = {124--132},
doi = {10.1007/978-3-031-49272-3_9},
eprint = {2309.00546},
archiveprefix = {arXiv},
abstract = {We consider bichromatic point sets with n red and n blue points and study straight-line bichromatic perfect matchings on them. We show that every such point set in convex position admits a matching with at least {\$}{\$}{\backslash}frac{\{}3n^2{\}}{\{}8{\}}-{\backslash}frac{\{}n{\}}{\{}2{\}}+c{\$}{\$}3n28-n2+ccrossings, for some {\$}{\$} -{\backslash}frac{\{}1{\}}{\{}2{\}} {\backslash}le c {\backslash}le {\backslash}frac{\{}1{\}}{\{}8{\}}{\$}{\$}-12≤c≤18. This bound is tight since for any {\$}{\$}k> {\backslash}frac{\{}3n^2{\}}{\{}8{\}} -{\backslash}frac{\{}n{\}}{\{}2{\}}+{\backslash}frac{\{}1{\}}{\{}8{\}}{\$}{\$}k>3n28-n2+18there exist bichromatic point sets that do not admit any perfect matching with k crossings.},
isbn = {978-3-031-49272-3},
originalfile = {/geometry/cggg.bib}
}
This file was generated by bibtex2html 1.98.