Regular augmentation of planar graphs

DOI10.1007/s00453-014-9922-4zbMath1328.05055MaRDI QIDQ747622

Tanja Hartmann, Ignaz Rutter, Jonathan Rollin

Publication date: 19 October 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-014-9922-4

zbMATH Keywords

complexity; connectivity; graph augmentation; efficient algorithms; regular planar graphs

Mathematics Subject Classification ID

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

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

05C40: Connectivity

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

05C76: Graph operations (line graphs, products, etc.)

Related Items

Augmenting Geometric Graphs with Matchings, Minimum weight connectivity augmentation for planar straight-line graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph connectivity and its augmentation: Applications of MA orderings
• Augmenting the connectivity of geometric graphs
• Edge-connectivity augmentation problems
• Plane Geometric Graph Augmentation: A Generic Perspective
• Augmenting the Connectivity of Planar and Geometric Graphs
• Tri-Edge-Connectivity Augmentation for Planar Straight Line Graphs
• Approximation Algorithms for Several Graph Augmentation Problems
• Planar Formulae and Their Uses
• The Problem of Compatible Representatives
• Augmentation Problems
• OPTIMAL BINARY SPACE PARTITIONS FOR SEGMENTS IN THE PLANE
• Connectivity augmentation in plane straight line graphs
• Some Theorems on Abstract Graphs