Monotone Arc Diagrams with few Biarcs
Abstract
We show that every planar graph has a monotone topological 2-page book embedding, also known as a monotone arc diagram, where at most $(4n-10)/5$ (of potentially $3n-6$) edges cross the spine, and every edge crosses the spine at most once; such an edge is called a biarc. We can also guarantee that all edges that cross the spine cross it in the same direction (e.g., from bottom to top). For planar 3-trees we further improve the bound to $(3n-9)/4$, and for so-called Kleetopes we obtain a bound of at most $(n-8)/3$ biarcs. The bound for Kleetopes is tight, even if the drawing is not required to be monotone. A Kleetope is a plane triangulation that is derived from another plane triangulation $T$ by inserting a new vertex $v_f$ into each face $f$ of $T$ and then connecting $v_f$ to the three vertices of $f$.
Fields of Study & Subjects
Geometric and Algebraic Topology
Formal Methods in Verification
Polynomial and algebraic computation
Publication details
- Journal / source
- Journal of Graph Algorithms and Applications
- Publisher
- Journal of Graph Algorithms and Applications
- Volume
- 29
- Issue
- 3
- Pages
- 111–142
- Publication date
- 22 June 2026
- Language
- EN