On the Hardness and Approximability of Planar Biconnectivity Augmentation

DOI10.1007/978-3-642-02882-3_25zbMath1248.68381OpenAlexW1560695543WikidataQ56977195 ScholiaQ56977195MaRDI QIDQ5323069

Bernd Zey, Petra Mutzel, Carsten Gutwenger

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

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

Related Items (4)

Augmenting the edge connectivity of planar straight line graphs to three ⋮ Connectivity augmentation in planar straight line graphs ⋮ Minimum weight connectivity augmentation for planar straight-line graphs ⋮ Triangulating Planar Graphs While Keeping the Pathwidth Small

Cites Work

• Some simplified NP-complete graph problems
• Finding a Smallest Augmentation to Biconnect a Graph
• On-Line Planarity Testing
• Dividing a Graph into Triconnected Components
• Unnamed Item
• Unnamed Item
• Unnamed Item

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