Chain Decompositions of 4-Connected Graphs

Authors:
  • SCSean Curran
    Sean Curran
  • OLOrlando Lee
    Orlando Lee
  • XYXingxing Yu
    Xingxing Yu

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.

This publication has 7 references indexed in Scilit: