Chain Decompositions of 4-Connected Graphs
Authors:
- Sean CurranSCSean Curran
- Orlando LeeOLOrlando Lee
- Xingxing YuXYXingxing Yu
- 1 January 2005
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 19 (4) , 848-880
Abstract
In this paper we give a decomposition of a 4-connected graph G into nonseparating chains, which is similar to an ear decomposition of a 2-connected graph. We also give an $O(|V(G)|^2|E(G)|)$ algorithm that constructs such a decomposition. In applications, the asymptotic performance can often be improved to $O(|V(G)|^3)$.This decomposition will be used to find four independent spanning trees in a 4-connected graph.
Keywords
This publication has 7 references indexed in Scilit:
- Nonseparating Planar Chains in 4-Connected GraphsSIAM Journal on Discrete Mathematics, 2005
- A new planarity testTheoretical Computer Science, 1999
- Finding nonseparating induced cycles and independent spanning trees in 3-connected graphsJournal of Algorithms, 1988
- Data Structures and Network Algorithms1983
- Efficient Planarity TestingJournal of the ACM, 1974
- Dividing a Graph into Triconnected ComponentsSIAM Journal on Computing, 1973
- How to Draw a GraphProceedings of the London Mathematical Society, 1963