Previous button up button Next button
The absence of efficient dual pairs of spanning trees in planar graphs

T.R.Riley and W.P.Thurston

Electronic Journal of Combinatorics, 13, N13, 2006.

A spanning tree T in a finite planar connected graph G determines a dual spanning tree T* in the dual graph G* such that T and T* do not intersect. We show that it is not always possible to find T in G, such that the diameters of T and T* are both within a uniform multiplicative constant (independent of G) of the diameters of their ambient graphs.

7 pages, 3 figures