@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{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{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{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{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}
}
@article{psw-rssds-22,
author = {Rosna Paul and Gelasio Salazar and Alexandra Weinberger},
title = {{{Rotation systems and simple drawings in surfaces}}},
journal = {submitted},
pages = {1--19},
year = 2022,
eprint = {2207.00312},
archiveprefix = {arXiv},
originalfile = {/geometry/cggg.bib}
}
@inproceedings{aoopsstv-epcgg-22,
author = {Aichholzer, Oswin and Obenaus, Johannes and Orthaber, Joachim
and Paul, Rosna and Schnider, Patrick and Steiner, Raphael and Taubner,
Tim and Vogtenhuber, Birgit},
title = {{{{Edge Partitions of Complete Geometric Graphs}}}},
booktitle = {38th International Symposium on Computational Geometry
(SoCG 2022)},
pages = {6:1--6:16},
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},
url = {https://drops.dagstuhl.de/opus/volltexte/2022/16014},
urn = {urn:nbn:de:0030-drops-160141},
doi = {10.4230/LIPIcs.SoCG.2022.6},
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{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}
}
@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{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.