On the Hardness and Approximability of Planar Biconnectivity Augmentation

DOI10.1007/978-3-642-02882-3_25MaRDI QIDQ5323069zbMATH OpenOpenAlexWikidataFDO

Authors Carsten Gutwenger, Petra Mutzel, Bernd Zey

Publication date 23 July 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-02882-3_25

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• scientific article; zbMATH DE number 177556
• Cubic augmentation of planar graphs
• scientific article; zbMATH DE number 1303565
• Augmenting trees to meet biconnectivity and diameter constraints
• Planar biconnectivity augmentation with fixed embedding

Cites work

• Dividing a Graph into Triconnected Components
• Finding a Smallest Augmentation to Biconnect a Graph
• scientific article; zbMATH DE number 177556 (Why is no real title available?)
• scientific article; zbMATH DE number 1303565 (Why is no real title available?)
• scientific article; zbMATH DE number 2080088 (Why is no real title available?)
• On-Line Planarity Testing
• Some simplified NP-complete graph problems

Cited in

(9)

• Minimum weight connectivity augmentation for planar straight-line graphs
• Triangulating planar graphs while keeping the pathwidth small
• Planar biconnectivity augmentation with fixed embedding
• scientific article; zbMATH DE number 177556 (Why is no real title available?)
• scientific article; zbMATH DE number 1303565 (Why is no real title available?)
• Optimal Augmentation for Bipartite Componentwise Biconnectivity in Linear Time
• Augmenting the edge connectivity of planar straight line graphs to three
• Connectivity augmentation in planar straight line graphs
• The price of connectivity augmentation on planar graphs

This page was built for publication: On the Hardness and Approximability of Planar Biconnectivity Augmentation

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