2026-07-24T02:23:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21295 2024-10-28T09:51:04Z ddc:004 open_access

Monotone Arc Diagrams with Few Biarcs Chaplick, Steven Förster, Henry Hoffmann, Michael Kaufmann, Michael planar graph topological book embedding monotone drawing linear layout We show that every planar graph has a monotone topological 2-page book embedding 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 can further improve the bound to (3n-9)/4, and for so-called Kleetopes we obtain a bound of at most (n-8)/3 edges that cross the spine. 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Steven Chaplick and Henry Förster and Michael Hoffmann and Michael Kaufmann 2024 Is Part Of LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.GD.2024.11 urn:nbn:de:0030-drops-212955 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.11 eng https://creativecommons.org/licenses/by/4.0/legalcode