Chain decompositions and independent trees in 4-connected graphs

ABSTRACT

This work was motivated by the study of a multitree approach to reliability in distributed networks and by the study of non-separating paths and cycles in highly connected graphs. We first give a result on "non-separating chains" in 4-connected graphs. This result is then used to obtain a "non-separating chain decomposition" of a 4-connected graph G, and an O(|V(G)|²|E(G)|) algorithm for constructing such a decomposition. As an application of this decomposition, we show how to produce four "independent spanning trees" in a 4-connected graph in O(|V(G)|³) time.

REFERENCES

• 1: S. Curran, O. Lee, and X. Yu, Non-separating planar chains in 4-connected graphs, submitted.
• 2: S. Curran, O. Lee, and X. Yu, Chain decomposition of 4-connected graphs, in preparation.
• 3: S. Curran, O. Lee, and X. Yu, Independent trees in 4-connected graphs, in preparation.
• 4: J. Cheriyan , S. N. Maheshwari, Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs, Journal of Algorithms, v.9 n.4, p.507-537, Dec. 1988 [doi>10.1016/0196-6774(88)90015-6]
• 5: N. Chiba , T. Nishizeki, The Hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs, Journal of Algorithms, v.10 n.2, p.187-211, June 1989 [doi>10.1016/0196-6774(89)90012-6]
• 6: Danny Dolev , Joe Halpern , Barbara Simons , Ray Strong, A new look at fault tolerant network routing, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.526-535, December 1984 [doi>10.1145/800057.808723]
• 7: A. Huck, Independent trees in graphs, Graphs and Combinatorics, 10 (1994), pp. 29--45.
• 8: T. Ibaraki and H. Nagamochi, A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph, Algorithmica, 7 (1992), pp. 583--596.
• 9: A. Itai and M. Rodeh, The multi-tree approach to reliability in distributed networks, Proc. 25th Annual IEEE Symp. Found. Comp. Sci., (1984), pp. 137--147.
• 10: A. Itai and A. Zehavi, Three tree-paths, J. Graph Theory, 13 (1989), pp. 175--188.
• 11: L. Lovász, Problems, in Recent Advances in Graph Theory, (ed. M. Fiedler), Academia, Prague, 1975.
• 12: K. Miura, S. Nakano, T. Nishizeki, and D. Takahashi, A linear-time algorithm to find four independent spanning trees in four connected planar graphs, Int. J. Found. Comp. Sci., 10 (1999), pp. 195--210.
• 13: Yossi Shiloach, A Polynomial Solution to the Undirected Two Paths Problem, Journal of the ACM (JACM), v.27 n.3, p.445-456, July 1980 [doi>10.1145/322203.322207]
• 14: C. Thomassen, A theorem on paths in planar graphs, J. Graph Theory, 7 (1983), pp. 169--176.
• 15: W. T. Tutte, How to draw a graph, Proc. London Math Soc., 13 (1963), pp. 743--767.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems; Trees

General Terms:
Algorithms, Theory