2015/05/16 by Therese Biedl, Thérèse Biedl, Biedl, Therese
Computer Science · Mathematics · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Graph Labeling and Dimension Problems #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1505.04235
To appear (without the appendix) at WG 2015
arxiv created 2015/05/16 · arxiv updated 2015/05/19
Any simple planar graph can be triangulated, i.e., we can add edges to it, without adding multi-edges, such that the result is planar and all faces are triangles. In this paper, we study the problem of triangulating a planar graph without increasing the pathwidth by much. We show that if a planar graph has pathwidth k, then we can triangulate it so that the resulting graph has pathwidth O(k) (where the factors are 1, 8 and 16 for 3-connected, 2-connected and arbitrary graphs). With similar techniques, we also show that any outer-planar graph of pathwidth k can be turned into a maximal outer-planar graph of pathwidth at most 4k+4. The previously best known result here was 16k+15.