@inproceedings{ap-tcep-19,
author = {Oswin Aichholzer and Daniel Perz},
title = {{{Triangles in the colored Euclidean plane}}},
booktitle = {Proc. {$35^{th}$} European Workshop on Computational Geometry EuroCG '19},
year = 2019,
pages = {10:1-10:7},
address = {Utrecht, The Netherlands},
pdf = {/files/publications/geometry/ap-tcep-19.pdf},
url = {http://www.eurocg2019.uu.nl/papers/10.pdf},
abstract = {{We study a variation of the well known Hadwiger-Nelson problem on the chromatic number
of the Euclidean plane. An embedding of a given triangle $T$ into the colored plane is called
monochromatic, if the three corners of the triangle get the same color. We provide a classification
of triangles according to the number of colors needed to color the plane so that the triangle can
not be embedded monochromatically. For example, we show that for near-equilateral triangles
three colors are enough and that for almost all triangles six colors are sufficient.}},
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{aoppt-dtcppm-20,
author = {O. Aichholzer and J. Obmann and P. Pat\'ak and D. Perz and J. Tkadlec},
title = {{{Disjoint tree-compatible plane perfect matchings}}},
booktitle = {Proceedings of the {36th} European Workshop on Computational Geometry (EuroCG$\,$2020)},
pages = {56:1--56:7},
year = 2020,
address = {W\"urzburg, Germany},
pages = {},
url = {http://www1.pub.informatik.uni-wuerzburg.de/eurocg2020/data/uploads/papers/eurocg20_paper_56.pdf},
abstract = {Two plane drawings of geometric 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.
For a given set $S$ of $2n$ points two plane drawings of perfect matchings $M_1$ and $M_2$ (which do not need to be disjoint nor compatible) are \emph{disjoint tree-compatible} if there exists a plane drawing of a spanning tree $T$ on~$S$ which is disjoint compatible to both $M_1$ and $M_2$.
We show that the graph of all disjoint tree-compatible perfect geometric matchings on $2n$ points in convex position is connected if and only if $2n \geq 10$. Moreover, in that case the diameter of this graph is either 4 or 5, independent of $n$.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{rpt-ertcps-20,
author = {R. Fabila-Monroy and D. Perz and A. L. Trujillo},
title = {{{Empty Rainbow Triangles in k-colored Point Sets}}},
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_38.pdf},
abstract = {Let $S$ be a set of $n$ points in general position in the plane. Suppose that
each point of $S$ has been assigned one of $k \ge 3$ possible colors and that there is
the same number, $m$, of points of each color class, so $n=km$. A triangle with vertices on $S$
is empty if it does not contain points of $S$ in its interior and it is
rainbow if all its vertices have different colors. Let $f(k,m)$ be the minimum
number of empty rainbow triangles determined by $S$. In this paper we show that
$f(k,m)=\Theta(k^3)$.
Furthermore we give a construction which does not contain an empty rainbow quadrilateral.},
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}
}
@article{fpt-ertcps21,
title = {{{Empty rainbow triangles in k-colored point sets}}},
journal = {Computational Geometry},
volume = {95},
pages = {101731},
year = {2021},
issn = {0925-7721},
doi = {https://doi.org/10.1016/j.comgeo.2020.101731},
url = {https://www.sciencedirect.com/science/article/pii/S0925772120301255},
author = {Ruy Fabila-Monroy and Daniel Perz and Ana Laura Trujillo-Negrete},
keywords = {k-holes, Empty triangles, Erd\H{o}s-Szekeres},
abstract = {Let S be a set of n points in general position in the plane. Suppose that each point of S has been assigned one of $k\geq 3$ possible colors and that there is the same number, m, of points of each color class. This means n=km. A polygon with vertices on S is empty if it does not contain points of S in its interior; and it is rainbow if all its vertices have different colors. Let f(k,m) be the minimum number of empty rainbow triangles determined by S. In this paper we give tight asymptotic bounds for this function. Furthermore, we show that S may not determine an empty rainbow quadrilateral for some arbitrarily large values of k and m.},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{cgklmp-nndd-21,
author = {Jonas Cleve and Nicolas Grelier and Kristin Knorr and Maarten L\"offler and Wolfgang Mulzer and Daniel Perz},
title = {{{Nearest-Neighbor Decompositions of Drawings}}},
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_40.pdf},
abstract = {Let $\mathcal{D}$ be a straight-line drawing of a graph in the plane, and let $c$ be a positive integer. We say that $\mathcal{D}$ has a nearest-neighbor decomposition into $c$ parts if there are point sets $P_1, \dots, P_c$ such that $\mathcal{D}$ is the union of the nearest neighbor graphs on $P_1, \dots, P_c$. We study the complexity of deciding whether it is possible to draw $D$ as the union of $c$ nearest-neighbor graphs.},
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{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{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{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}
}
@inproceedings{hlptw-fbus-22,
author = {Eva-Maria Hainzl and Maarten L{\"o}ffler and Daniel Perz and Josef Tkadlec and
and Markus Wallinger},
title = {{{Finding a Battleship of Uncertain Shape}}},
booktitle = {Proc. $38^{th}$ European Workshop on Computational Geometry (EuroCG 2022)},
pages = {48:1--48:7},
year = 2022,
address = {Perugia, Italy},
eprint = {2202.08747},
archiveprefix = {arXiv},
pdf = {https://eurocg2022.unipg.it/booklet/EuroCG2022-Booklet.pdf#page=351},
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}
}
@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}
}
@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{abps-fom-24B,
title = {{{Flips in Odd Matchings}}},
author = {Aichholzer, Oswin and Brötzner, Anna and Perz, Daniel and Schnider, Patrick},
booktitle = {Proceedings of the 36th Canadian Conference on Computational Geometry (CCCG 2024)},
pages = {299--303},
year = {2024},
abstract = {Let $\mathcal{P}$ be a set of $n=2m+1$ points in the plane in general position.
We define the graph $GM_\mathcal{P}$ whose vertex set is the set of all plane matchings on $\mathcal{P}$ with exactly $m$~edges. Two vertices in $GM_\mathcal{P}$ are connected if the two corresponding matchings have $m-1$ edges in common. In this work we show that $GM_\mathcal{P}$ is connected.},
url = {https://cosc.brocku.ca/~rnishat/CCCG_2024_proceedings.pdf},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{abps-fom-24A,
title = {{{Flips in Odd Matchings}}},
author = {Aichholzer, Oswin and Brötzner, Anna and Perz, Daniel and Schnider, Patrick},
booktitle = {Proceedings of the 40th European Workshop on Computational Geometry (EuroCG 2024)},
pages = {59:1--59:6},
year = {2024},
abstract = {Let $P$ be a set of $n=2m+1$ points in the plane in general position.
We define the graph $GM_P$ whose vertex set is the set of all plane matchings on $P$ with exactly $m$~edges. Two vertices in $GM_P$ are connected if the two corresponding matchings have $m-1$ edges in common. In this work we show that $GM_P$ is connected.},
url = {https://eurocg2024.math.uoi.gr/data/uploads/paper_59.pdf},
originalfile = {/geometry/cggg.bib}
}
This file was generated by bibtex2html 1.98.