Triangulating planar graphs while keeping the pathwidth small

DOI10.1007/978-3-662-53174-7_30MaRDI QIDQ2827827zbMATH OpenOpenAlexFDO

Authors Therese Biedl

Publication date 21 October 2016

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1505.04235

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Abstract: 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$.

Recommendations

• On the path-width of planar graphs
• Pathwidth of planar and line graphs
• On triangulating \(k\)-outerplanar graphs
• Triangulating planar graphs while minimizing the maximum degree
• 2-connecting outerplanar graphs without blowing up the pathwidth

Cites work

• 2-connecting outerplanar graphs without blowing up the pathwidth
• A 4-approximation for the height of drawing 2-connected outer-planar graphs
• Drawing planar 3-trees with given face areas
• How to draw a planar graph on a grid
• scientific article; zbMATH DE number 432759 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 1361465 (Why is no real title available?)
• On the Hardness and Approximability of Planar Biconnectivity Augmentation
• On triangulating \(k\)-outerplanar graphs
• On triangulating planar graphs under the four-connectivity constraint
• On-Line Planarity Testing
• PATHWIDTH AND LAYERED DRAWINGS OF TREES
• Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions
• Triangulating planar graphs while minimizing the maximum degree

Cited in

(7)

• Pathwidth of planar and line graphs
• Pathwidth of outerplanar graphs
• On the path-width of planar graphs
• The effect of planarization on width
• Triangulating planar graphs while minimizing the maximum degree
• Upward and orthogonal planarity are W[1]-hard parameterized by treewidth
• Upward and rectilinear planarity are W[1]-hard parameterized by treewidth

This page was built for publication: Triangulating planar graphs while keeping the pathwidth small

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2827827)