Regular augmentation of planar graphs

DOI10.1007/s00453-014-9922-4zbMath1328.05055OpenAlexW2002953601MaRDI 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

complexityconnectivitygraph augmentationefficient algorithmsregular planar graphs

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 algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph operations (line graphs, products, etc.) (05C76)

Related Items (2)

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

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

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