Separable Drawings: Extendability and Crossing-Free Hamiltonian Cycles
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913544575909888 |
|---|---|
| author | Aichholzer, Oswin Orthaber, Joachim Vogtenhuber, Birgit |
| author_facet | Aichholzer, Oswin Orthaber, Joachim Vogtenhuber, Birgit |
| contents | Generalizing pseudospherical drawings, we introduce a new class of simple drawings, which we call separable drawings. In a separable drawing, every edge can be closed to a simple curve that intersects each other edge at most once. Curves of different edges might interact arbitrarily. Most notably, we show that (1) every separable drawing of any graph on $n$ vertices in the plane can be extended to a simple drawing of the complete graph $K_{n}$, (2) every separable drawing of $K_{n}$ contains a crossing-free Hamiltonian cycle and is plane Hamiltonian connected, and (3) every generalized convex drawing and every 2-page book drawing is separable. Further, the class of separable drawings is a proper superclass of the union of generalized convex and 2-page book drawings. Hence, our results on plane Hamiltonicity extend recent work on generalized convex drawings by Bergold et al. (SoCG 2024). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_09922 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Separable Drawings: Extendability and Crossing-Free Hamiltonian Cycles Aichholzer, Oswin Orthaber, Joachim Vogtenhuber, Birgit Computational Geometry Discrete Mathematics Combinatorics Generalizing pseudospherical drawings, we introduce a new class of simple drawings, which we call separable drawings. In a separable drawing, every edge can be closed to a simple curve that intersects each other edge at most once. Curves of different edges might interact arbitrarily. Most notably, we show that (1) every separable drawing of any graph on $n$ vertices in the plane can be extended to a simple drawing of the complete graph $K_{n}$, (2) every separable drawing of $K_{n}$ contains a crossing-free Hamiltonian cycle and is plane Hamiltonian connected, and (3) every generalized convex drawing and every 2-page book drawing is separable. Further, the class of separable drawings is a proper superclass of the union of generalized convex and 2-page book drawings. Hence, our results on plane Hamiltonicity extend recent work on generalized convex drawings by Bergold et al. (SoCG 2024). |
| title | Separable Drawings: Extendability and Crossing-Free Hamiltonian Cycles |
| topic | Computational Geometry Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2410.09922 |