Cubic augmentation of planar graphs

DOI10.1007/978-3-642-35261-4_43MaRDI QIDQ4909557zbMATH OpenOpenAlexFDO

Authors Tanja Hartmann, Jonathan Rollin, Ignaz Rutter

Publication date 21 March 2013

Published in Algorithms and Computation (Search for Journal in Brave)

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

zbMATH Keywords

planar graphsaugmentation of graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph operations (line graphs, products, etc.) (05C76)

Abstract: In this paper we study the problem of augmenting a planar graph such that it becomes 3-regular and remains planar. We show that it is NP-hard to decide whether such an augmentation exists. On the other hand, we give an efficient algorithm for the variant of the problem where the input graph has a fixed planar (topological) embedding that has to be preserved by the augmentation. We further generalize this algorithm to test efficiently whether a 3-regular planar augmentation exists that additionally makes the input graph connected or biconnected. If the input graph should become even triconnected, we show that the existence of a 3-regular planar augmentation is again NP-hard to decide.

Recommendations

• Regular augmentation of planar graphs
• Augmenting the connectivity of planar and geometric graphs
• scientific article; zbMATH DE number 177556
• Planar biconnectivity augmentation with fixed embedding
• scientific article; zbMATH DE number 1303565

Cited in

(5)

• On regular subgraphs of augmented cubes
• Regular augmentation of planar graphs
• Plane augmentation of plane graphs to meet parity constraints
• scientific article; zbMATH DE number 177556 (Why is no real title available?)
• On the Hardness and Approximability of Planar Biconnectivity Augmentation

This page was built for publication: Cubic augmentation of planar graphs

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