1-2hit |
Given a graph G, a designated vertex r and a natural number k, we wish to find k "independent" spanning trees of G rooted at r, that is, k spanning trees such that, for any vertex v, the k paths connecting r and v in the k trees are internally disjoint in G. In this paper we give a linear-time algorithm to find k independent spanning trees in a k-connected maximal planar graph rooted at any designated vertex.
Given a graph G=(V,E), five distinct vertices u1,u2,u3,u4,u5 V and five natural numbers n1,n2,n3,n4,n5 such that Σ5i=1ni=|V|, we wish to find a partition V1,V2,V3,V4,V5 of the vertex set V such that ui Vi, |Vi|=ni and Vi induces a connected subgraph of G for each i, 1i5. In this paper we give a simple linear-time algorithm to find such a partition if G is a 5-connected internally triangulated plane graph and u1,u2,u3,u4,u5 are located on the outer face of G. Our algorithm is based on a "5-canonical decomposition" of G, which is a generalization of an st-numbering and a "canonical ordering" known in the area of graph drawings.