@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{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{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{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{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{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{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{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{nnwmmlr-rpfcaic-22,
author = {Phoebe de Nooijer and Soeren Nickel and Alexandra Weinberger and Zuzana Mas{\'{a}}rov{\'{a}} and Tamara Mchedlidze and Maarten L{\"o}ffler and G{\"u}nter Rote},
title = {{{Removing Popular Faces in Curve Arrangements by Inserting one more Curve}}},
booktitle = {Proc. $38^{th}$ European Workshop on Computational Geometry (EuroCG 2022)},
pages = {38:1--38:8},
year = 2022,
address = {Perugia, Italy},
eprint = {2202.12175},
archiveprefix = {arXiv},
pdf = {https://eurocg2022.unipg.it/booklet/EuroCG2022-Booklet.pdf#page=273},
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{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{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}
}
@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}
}
@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}
}
This file was generated by bibtex2html 1.98.