|
|
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
|
