What induces plane structures in complete graph drawings?

Alexandra Weinberger, Ji Zeng · 2026

Read What induces plane structures in complete graph drawings? by Alexandra Weinberger, Ji Zeng (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-05208.txt.

Introduction

Alexandra Weinberger and Ji Zeng ask when complete graph drawings must contain many pairwise disjoint curves. They prove disjoint curves are unavoidable under either of two rules: adjacent curves, sharing an endpoint, never cross, or non-adjacent curves cross at most once. Conversely, they construct drawings where adjacent curves cross exactly once and non-adjacent curves cross once or twice, so no two curves are disjoint. They also analyze how disjoint curves emerge without those assumptions and characterize the plane structures each rule guarantees.

Catalog record

CREATORAlexandra Weinberger, Ji Zeng
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE42658
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.05208

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

What induces plane structures in complete graph drawings? Alexandra Weinberger, Ji Zeng Abstract This paper considers the task of connecting points on a piece of paper by drawing a curve between each pair of them. Under mild assumptions, we prove that many pairwise disjoint curves are unavoidable if either of the following rules is obeyed: any two adjacent curves do not cross, or any two non-adjacent curves cross at most once. Here, two curves are called adjacent if they share an endpoint. On the other hand, we demonstrate how to draw all curves such that any two adjacent curves cross exactly once, any two non-adjacent curves cross at least once and at most twice, and thus no two curves are disjoint. Furthermore, we analyze the emergence of disjoint curves without these mild assumptions, and characterize the plane structures in complete graph drawings guaranteed by each of the rules above. FernUniversität in Hagen, [email protected]://orcid.org/0000-0001-8553-6661Alfréd Rényi Institute of Mathematics, [email protected]://orcid.org/0009-0002-7240-4832Supported by ERC Advanced Grants “GeoScape”, no. 882971 and “ERMiD”, no. 101054936, and also partly supported by NSF grant DMS-1928930 while in residence at the Simons–Laufer Mathematical Sciences Institute during the Spring 2025 semester. We wish to thank Jeck Lim, Jonathan Rollin, and André Schulz for helpful discussions, and an anonymous reviewer who provided the idea to simplify Lemma 8 . † † runningauthor: A. Weinberger and J. Zeng † † copyright: Alexandra Weinberger and Ji Zeng 1 Introduction In the plane, a complete graph drawing is a collection of points and curves connecting each pair of these points. The points are called vertices and the curves are called edges of this drawing. More precisely, an edge is the image of a piecewise smooth map from a closed interval on the real line to the plane which starts and ends at its corresponding pair of vertices. In this paper, we make mild assumptions for complete graph drawings: we assume no edge contains vertices other than its endpoints; we assume no edge self-intersects, that is, its defining map must be injective; we assume edges cross properly whenever they intersect, in particular, edges do not merely touch. It is easy to imagine that a complete graph drawing can be tangled like a mass of spaghetti noodles. Our main result asserts that the breaking point of “tangledness” in complete graph drawings is the logical disjunction of the two rules below. Here, two edges are called adjacent if they share an endpoint. \displaystyle\text{Adjacent-simple: any two adjacent edges do not cross;} \displaystyle\text{Separate-simple: any two non-adjacent edges cross at most once.} Theorem 1 . For any positive integer m , there exists n such that every complete graph drawing on n vertices that is either adjacent-simple or separate-simple must contain m pairwise disjoint edges. On the other hand, there exist complete graph drawings on arbitrarily many vertices in which any two adjacent edges cross exactly once, and any two non-adjacent edges cross at least once and at most twice. Figure 1 : Any two adjacent edges cross exactly once, any two non-adjacent edges cross at least once and at most twice. In general, a graph in the abstract sense consists of a vertex set and an edge set, where each edge is a vertex pair (unordered). A drawing of a graph is a representation of its vertices as distinct points in the plane, and its edges as curves connecting the corresponding pair of vertices. We make the same mild assumptions for all drawings of graphs. A drawing is said to be plane if it has no crossings. Planarity has been a main theme in the development of graph theory featured by famous theorems such as Euler’s formula and the four color theorem. A drawing is said to be simple if it is adjacent-simple and separate-simple simultaneously. Rafla [ 31 ] conjectured that every simple complete graph drawing on at least three vertices must contain a plane Hamiltonian cycle, that is, a cycle that visits every vertex exactly once. Motivated by this conjecture or not, unavoidable plane structures in simple drawings are extensively studied, see our incomplete list [ 1 , 3 , 16 , 18 , 17 , 19 , 29 , 33 , 39 , 37 , 42 ] . We emphasize the work [ 29 ] of Pach and Tóth, in which they proved simple complete graph drawings induce many pairwise disjoint edges and constructed complete graph drawings where any two edges cross at least once and at most twice. However, some adjacent edges cross twice in their construction. With respect to the conditions, Theorem 1 can be considered as an improvement of their result (albeit quantitatively they obtain more disjoint edges). Further work on unavoidable plane structures also addresses simple complete graph drawings that satisfy additional conditions [ 4 , 7 , 9 ] , and especially those where the edges have to be straight [ 26 , 35 , 41 ] . Drawings that are only adjacent-simple or only separate-simple, have been studied under the names semi-simple [ 5 ] and star-simple [ 13 ] , or tolerable [ 10 ] , respectively. This paper attempts to capture the earliest moment at which one can expect unavoidable plane structures. We shall state the two cases of Theorem 1 as theorems on their own. We call a graph S a plane structure guaranteed in a collection \mathcal{C} of graph drawings if there exists an integer n such that any drawing in \mathcal{C} of at least n vertices must contain a plane sub-drawing of S . Here, a drawing A is called a sub-drawing of another drawing B if the vertex set and edge set of A are subsets of those of B respectively. A squid is a connected graph that contains exactly one cycle which is a triangle, and all other vertices only form edges with two fixed vertices on this triangle. A caterpillar is a connected graph without cycles that contains a central path, and all other vertices only form edges with vertices on this path. An isolated vertex in a graph is a vertex that does not form any edges. Figure 2 : A squid (left) and a caterpillar (right). Theorem 2 . The plane structures guaranteed in adjacent-simple complete graph drawings are exactly squids with extra isolated vertices, and unions of disjoint caterpillars. Theorem 3 . The plane structures guaranteed in separate-simple complete graph drawings are exactly unions of disjoint edges and isolated vertices. One may ask to what extent our main result still holds if the mild assumptions are dropped. For example, when we connect points on a piece of paper, the curves drawn by a pen could touch or run through any points, then what would be the earliest cause of disjointness in this scenario? To model an edge in a drawing without mild assumptions, we use the image \text{Im}(f) of a function f from the unit interval [0,1] to the plane \mathbb{R}^{2} . We also define self-intersection of f as \Delta(f)=\{p:p=f(x)=f(y)\penalty\ \text{for $x\neq y$}\} . A family of functions \{f_{i}\} is called stroke-like if all the pre-images f_{i}^{-1}(\text{Im}(f_{j})) and f_{i}^{-1}(\Delta(f_{i})) are unions of finitely many sub-intervals of [0,1] . Although mathematically two curves can intersect infinitely many times without coincide

Read the complete text