EUVIMEDOpdag EUVIMED
Crossref

Extending Simple Monotone Drawings

Jan Kynčl, Jan Soukup

The Electronic Journal of Combinatorics · 2026-07-03 · 33 (3)

DOI: 10.37236/14683 ↗

At a glance

Journal article in The Electronic Journal of Combinatorics, published online on 2026-07-03. Written by Jan Kynčl and 1 co-authors.

AbstractBibliografiske oplysningerCiteRelated studies

Abstract (original language)

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.

Cite

APA

Kynčl, J., & Soukup, J. (2026). Extending Simple Monotone Drawings. The Electronic Journal of Combinatorics, 33(3). https://doi.org/10.37236/14683

Vancouver

Kynčl J, Soukup J. Extending Simple Monotone Drawings. The Electronic Journal of Combinatorics. 2026;33(3). doi:10.37236/14683

BibTeX
@article{Kynl2026,
  author = {Kynčl, Jan and Soukup, Jan},
  title = {Extending Simple Monotone Drawings},
  journal = {The Electronic Journal of Combinatorics},
  year = {2026},
  volume = {33},
  number = {3},
  doi = {10.37236/14683}
}
Start for free →