The absence of efficient dual pairs of spanning trees in planar graphs

MaRDI QIDQ2501002zbMATH OpenFDO

Authors William P. Thurston, Timothy Riley

Publication date 30 August 2006

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0511493, https://eudml.org/doc/126454, http://www.emis.de/journals/EJC/Volume_13/Abstracts/v13i1n13.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

diameters

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Cancellation theory of groups; application of van Kampen diagrams (20F06) Relations of low-dimensional topology with graph theory (57M15)

Abstract: 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.

Recommendations

• scientific article; zbMATH DE number 1953097
• Trees and Co-trees with Bounded Degrees in Planar 3-connected Graphs
• A structural property of trees with an application to vertex-arboricity
• On spanning trees without vertices of degree 2 in plane triangulations
• Publication:4504031

Cited in

(2)

• Contracting the boundary of a Riemannian 2-disc
• A Glimpse into Thurston’s Work

This page was built for publication: The absence of efficient dual pairs of spanning trees in planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2501002)