2006/08/25 by Tim Riley, William P. Thurston · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Stochastic processes and statistical mechanics #Computational Geometry and Mesh Generation #Combinatorics #Mathematics #Spanning tree #Multiplicative function #Planar graph #Dual graph #Graph #Discrete mathematics #Dual (grammatical number)
paper · pdf · doi:10.37236/1151
openalex publication_date 2006/08/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/15
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.