2026-08-07T15:58:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21318 2024-10-28T09:51:05Z ddc:004 open_access

Separable Drawings: Extendability and Crossing-Free Hamiltonian Cycles Aichholzer, Oswin Orthaber, Joachim Vogtenhuber, Birgit Simple drawings Pseudospherical drawings Generalized convex drawings Plane Hamiltonicity Extendability of drawings Recognition of drawing classes 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Oswin Aichholzer and Joachim Orthaber and Birgit Vogtenhuber 2024 Is Part Of LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.GD.2024.34 urn:nbn:de:0030-drops-213187 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.34 eng https://creativecommons.org/licenses/by/4.0/legalcode