Separable Drawings: Extendability and Crossing-Free Hamiltonian Cycles

Abstract

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. For different edges, the non-edge parts of these curves may interact arbitrarily though. 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 (that is, it contains a crossing-free Hamiltonian path between each pair of vertices), 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. (DCG 2025).

Final version as published in the journal JGAA