Search

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 confirm this conjecture for cylindrical drawings, strongly $c$-monotone drawings, as well as $x$-bounded drawings. Moreover, we introduce the stronger question of whether a crossing-free Hamiltonian path between each pair of vertices always exists., Comment: 24 pages, 20 figures. Full version of extended abstract presented at EuroCG 2023

In this paper, we disprove the long-standing conjecture that any complete geometric graph on 2n vertices can be partitioned into n plane spanning trees. Our construction is based on so-called bumpy wheel sets. We fully characterize which bumpy wheels can and in particular which cannot be partitioned into plane spanning trees (or even into arbitrary plane subgraphs). Furthermore, we show a sufficient condition for generalized wheels to not admit a partition into plane spanning trees, and give a complete characterization when they admit a partition into plane spanning double stars. Finally, we initiate the study of partitions 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., Leibniz International Proceedings in Informatics (LIPIcs), 224, ISSN:1868-8969, 38th International Symposium on Computational Geometry, ISBN:978-3-95977-227-3

In this paper, we disprove the long-standing conjecture that any complete geometric graph on $2n$ vertices can be partitioned into $n$ plane spanning trees. Our construction is based on so-called bumpy wheel sets. We fully characterize which bumpy wheels can and in particular which \emph{cannot} be partitioned into plane spanning trees (or even into arbitrary plane \emph{subgraphs}), including a complete description of all possible partitions (into plane spanning trees). Furthermore, we show a sufficient condition for \emph{generalized wheels} to not admit a partition into plane spanning trees, and give a complete characterization when they admit a partition into plane spanning double stars.