A plane graph representation of triconnected graphs

DOI10.1016/J.TCS.2010.08.029MaRDI QIDQ410724zbMATH OpenOpenAlexFDO

Authors Shunsuke Ota, Ehab Morsy, 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

algorithmspartitiondata structureconnectivitygraph embeddingplane graphsindependent trees

Mathematics Subject Classification ID

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

Recommendations

• Triangle-partitioning edges of planar graphs, toroidal graphs and \(k\)-planar graphs
• A robust algorithm for bisecting a triconnected graph with two resource sets
• scientific article; zbMATH DE number 1262808
• Partitioning Planar Graphs
• Plane triangulations are 6-partitionable

Cites work

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

Cited in

(6)

• Representation of Planar Hypergraphs by Contacts of Triangles
• Partition into almost straight trails
• Efficient algorithms for tripartitioning triconnected graphs and 3-edge-connected graphs
• scientific article; zbMATH DE number 2192094 (Why is no real title available?)
• scientific article; zbMATH DE number 3882450 (Why is no real title available?)
• Triangle-partitioning edges of planar graphs, toroidal graphs and \(k\)-planar graphs

This page was built for publication: A plane graph representation of triconnected graphs

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