Extending Simple Monotone Drawings
Abstract
We prove the following variant of Levi's Enlargement Lemma: for an arbitrary arrangement $\mathcal{A}$ of $x$-monotone pseudosegments in the plane and a pair of points $a,b$ with distinct $x$-coordinates and not on the same pseudosegment, there exists a simple $x$-monotone curve with endpoints $a,b$ that intersects every curve of $\mathcal{A}$ at most once. As a consequence, every simple monotone drawing of a graph can be extended to a simple monotone drawing of a complete graph. We also show that extending an arrangement of cylindrically monotone pseudosegments is not always possible; in fact, the corresponding decision problem is NP-hard.
Fields of Study & Subjects
graph theory and CDMA systems
Computational Geometry and Mesh Generation
Point processes and geometric inequalities
Publication details
- Journal / source
- The Electronic Journal of Combinatorics
- Volume
- 33
- Issue
- 3
- Publication date
- 3 July 2026
- Language
- EN