A LINEAR-TIME ALGORITHM TO FIND FOUR INDEPENDENT SPANNING TREES IN FOUR CONNECTED PLANAR GRAPHS
Kazuyuki Miura, Daishiro Takahashi, Shin-ichi Nakano, Takao Nishizeki · International Journal of Foundations of Computer Science · 1999
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 the k paths connecting r and any vertex v in the k trees are internally disjoint. In this paper we give a linear-time algorithm to find four independent spanning trees in a 4-connected planar graph.