A plane graph representation of triconnected graphs

DOI10.1016/j.tcs.2010.08.029zbMath1238.05215OpenAlexW2019713299MaRDI QIDQ410724

Ehab Morsy, Shunsuke Ota, Hiroshi Nagamochi

Publication date: 3 April 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.08.029

zbMATH Keywords

partitionalgorithmsconnectivitygraph embeddingplane graphsdata structureindependent trees

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Connectivity (05C40)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear-time algorithm for four-partitioning four-connected planar graphs
• A linear algorithm for bipartition of biconnected graphs
• On the complexity of partitioning graphs into connected subgraphs
• The multi-tree approach to reliability in distributed networks
• Fault-tolerant routings in a \(\kappa\)-connected network
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• Most uniform path partitioning and its use in image processing
• Plane triangulations are 6-partitionable
• A tabu search heuristic and adaptive memory procedure for political districting
• A robust algorithm for bisecting a triconnected graph with two resource sets
• Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs
• A homology theory for spanning tress of a graph
• Directional Routing via Generalized st-Numberings
• Dividing a Graph into Triconnected Components