2013/12/12 by Md. Jawaherul Alam, Alam, Md. Jawaherul, Michael A. Bekos +10
Computer Science · Engineering · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #FOS: Computer and information sciences #Optimization and Packing Problems #cs.CG
paper · pdf · doi:10.48550/arxiv.1312.3538
arxiv created 2013/12/12 · openalex publication_date 2013/12/12 · arxiv updated 2013/12/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In smooth orthogonal layouts of planar graphs, every edge is an alternating sequence of axis-aligned segments and circular arcs with common axis-aligned tangents. In this paper, we study the problem of finding smooth orthogonal layouts of low edge complexity, that is, with few segments per edge. We say that a graph has smooth complexity k---for short, an SCk-layout---if it admits a smooth orthogonal drawing of edge complexity at most k. Our main result is that every 4-planar graph has an SC2-layout. While our drawings may have super-polynomial area, we show that, for 3-planar graphs, cubic area suffices. Further, we show that every biconnected 4-outerplane graph admits an SC1-layout. On the negative side, we demonstrate an infinite family of biconnected 4-planar graphs that requires exponential area for an SC1-layout. Finally, we present an infinite family of biconnected 4-planar graphs that does not admit an SC1-layout.