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

zbMATH Open1097.05015arXivmath/0511493MaRDI QIDQ2501002FDOQ2501002

Timothy Riley, William P. Thurston

Publication date: 30 August 2006

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

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.

Full work available at URL: https://arxiv.org/abs/math/0511493

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)

Cited In (3)

• Contracting the boundary of a Riemannian 2-disc
• Fast and compact planar embeddings
• A Glimpse into Thurston’s Work

   Recommendations

• Title not available (Why is that?) 👍 👎
• 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 👍 👎
• Title not available (Why is that?) 👍 👎

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)