2012/12/27 by Jasine Babu, Babu, Jasine, Manu Basavaraju +5
Computer Science · Engineering · Environmental Science · Mathematics · #3D Modeling in Geospatial Applications #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Remote Sensing and LiDAR Applications #cs.DM #cs.DS #math.CO
paper · pdf · doi:10.48550/arxiv.1212.6382
openalex publication_date 2012/12/27 · arxiv created 2014/01/01 · arxiv updated 2014/01/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
Given a connected outerplanar graph G of pathwidth p, we give an algorithm to add edges to G to get a supergraph of G, which is 2-vertex-connected, outerplanar and of pathwidth O(p). This settles an open problem raised by Biedl, in the context of computing minimum height planar straight line drawings of outerplanar graphs, with their vertices placed on a two dimensional grid. In conjunction with the result of this paper, the constant factor approximation algorithm for this problem obtained by Biedl for 2-vertex-connected outerplanar graphs will work for all outer planar graphs.