Augmenting the connectivity of geometric graphs

DOI10.1016/j.comgeo.2007.09.001zbMath1147.05308OpenAlexW2063013286MaRDI QIDQ929747

Ferran Hurtado, Jorge Urrutia, Manuel Abellanas, F. Javier Tejel, Alfredo Daniel Garcia

Publication date: 18 June 2008

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2007.09.001

zbMATH Keywords

2-vertex and 2-edge connected graphsaugmentation problemsplane geometric graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items (21)

BOUNDED LENGTH, 2-EDGE AUGMENTATION OF GEOMETRIC PLANAR GRAPHS ⋮ On triconnected and cubic plane graphs on given point sets ⋮ Connectivity augmentation in plane straight line graphs ⋮ Plane augmentation of plane graphs to meet parity constraints ⋮ Shortest paths in the plane with obstacle violations ⋮ Compatible connectivity augmentation of planar disconnected graphs ⋮ The Mathematics of Ferran Hurtado: A Brief Survey ⋮ Connecting a set of circles with minimum sum of radii ⋮ Minimum Weight Connectivity Augmentation for Planar Straight-Line Graphs ⋮ Compatible spanning trees ⋮ Compatible geometric matchings ⋮ 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 ⋮ Unnamed Item ⋮ Regular augmentation of planar graphs ⋮ Augmenting the Connectivity of Planar and Geometric Graphs ⋮ Geometric biplane graphs. I: Maximal graphs ⋮ Geometric biplane graphs. II: Graph augmentation ⋮ Augmenting a tree to a \(k\)-arbor-connected graph with pagenumber \(k\) ⋮ Bichromatic compatible matchings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Alternating paths through disjoint line segments
• Edge-connectivity augmentation problems
• Successive edge-connectivity augmentation problems
• Deterministic \(\tilde O(nm)\) time edge-splitting in undirected graphs
• Independence free graphs and vertex connectivity augmentation
• A smallest augmentation to 3-connect a graph
• Competitive online routing in geometric graphs
• Encompassing colored planar straight line graphs
• Computing Simple Circuits from a Set of Line Segments is NP-Complete
• Augmentation Problems
• Augmenting Outerplanar Graphs
• Algorithm Theory - SWAT 2004
• Pointed and colored binary encompassing trees
• Every set of disjoint line segments admits a binary tree

This page was built for publication: Augmenting the connectivity of geometric graphs