The Absence of Efficient Dual Pairs of Spanning Trees in Planar Graphs

  • T. R. Riley
  • W. P. Thurston


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.

Article Number