On finding two-connected subgraphs in planar graphs

DOI10.1016/S0167-6377(96)00046-6MaRDI QIDQ1376267zbMATH OpenOpenAlexWikidataFDO

Authors J. Scott Provan

Publication date 17 December 1997

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0167-6377(96)00046-6, https://cdr.lib.unc.edu/downloads/7w62fj50p

zbMATH Keywords

design of reliable networksminimum-weight 2-connected subgraphnetwork survivabilityplanar graphpolynomial-time algorithmSteiner tree

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Recommendations

• On the two-connected planar spanning subgraph polytope
• On Finding Minimal Two-Connected Subgraphs
• The \(k\)-subconnectedness of planar graphs
• 2-connected spanning subgraphs of planar 3-connected graphs
• On two-connected subgraph polytopes
• scientific article; zbMATH DE number 140100
• Finding regular subgraphs in both arbitrary and planar graphs
• Approximation schemes for minimum 2-edge-connected and biconnected subgraphs in planar graphs
• scientific article; zbMATH DE number 434489
• Two-Connected Augmentation Problems in Planar Graphs

Cites work

• Biconnectivity approximations and graph carvings
• Convexity and the Steiner tree problem
• Generalized steiner problem in series-parallel networks
• Integer Polyhedra Arising from Certain Network Design Problems with Connectivity Constraints
• Minimal connected enclosures on an embedded planar graph
• Minimum-weight two-connected spanning networks
• Send-and-Split Method for Minimum-Concave-Cost Network Flows
• Shortest enclosing walks and cycles in embedded graphs
• The Planar Hamiltonian Circuit Problem is NP-Complete
• The Steiner tree problem

Cited in

(10)

• Minimal connected enclosures on an embedded planar graph
• 2-connected spanning subgraphs of planar 3-connected graphs
• On the two-connected planar spanning subgraph polytope
• More routes for evacuation
• Encoding and avoiding 2-connected patterns in polygon dissections and outerplanar graphs
• Defending planar graphs against star-cutsets
• scientific article; zbMATH DE number 434489 (Why is no real title available?)
• Minimum face-spanning subgraphs of plane graphs
• Approximation schemes for minimum 2-edge-connected and biconnected subgraphs in planar graphs
• Connected feedback vertex set in planar graphs

This page was built for publication: On finding two-connected subgraphs in planar graphs

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