2022/05/16 by Walter Didimo, Didimo, Walter, Michael Kaufmann +5
Computer Science · Engineering · Mathematics · #1-planar graph #3D Modeling in Geospatial Applications #Book embedding #Combinatorics #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #Discrete mathematics #FOS: Computer and information sciences #Graph #Interactive and Immersive Displays #Line graph #Mathematics #Outerplanar graph #Pathwidth #Planar graph #Planar straight-line graph #Vertex (graph theory) #cs.CG #cs.DS
paper · pdf · doi:10.48550/arxiv.2205.07500
published in arXiv (Cornell University) (Cornell University) · arXiv admin note: text overlap with arXiv:2008.03784
arxiv created 2022/05/16 · openalex publication_date 2022/05/16 · arxiv updated 2022/05/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
A planar orthogonal drawing of a planar 4-graph G (i.e., a planar graph with vertex-degree at most four) is a crossing-free drawing that maps each vertex of G to a distinct point of the plane and each edge of G to a sequence of horizontal and vertical segments between its end-points. A longstanding open question in Graph Drawing, dating back over 30 years, is whether there exists a linear-time algorithm to compute an orthogonal drawing of a plane 4-graph with the minimum number of bends. The term "plane" indicates that the input graph comes together with a planar embedding, which must be preserved by the drawing (i.e., the drawing must have the same set of faces as the input graph). In this paper, we positively answer the question above for the widely-studied class of series-parallel graphs. Our linear-time algorithm is based on a characterization of the planar series-parallel graphs that admit an orthogonal drawing without bends. This characterization is given in terms of the orthogonal spirality that each type of triconnected component of the graph can take; the orthogonal spirality of a component measures how much that component is "rolled-up" in an orthogonal drawing of the graph.