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

Simple item page
dc.creatorRiley, T. R.
dc.creatorThurston, W. P.
dc.date2005-11-20
dc.date2006-09-07
dc.date.accessioned2026-07-07T06:51:29Z
dc.date.available2026-07-07T06:51:29Z
dc.descriptionA 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.
dc.description7 pages, 3 figures
dc.identifierhttps://arxiv.org/abs/math/0511493
dc.identifierhttp://arxiv.org/abs/math/0511493
dc.identifierElectronic Journal of Computation, 13, N13, 2006
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/105003
dc.subjectCombinatorics
dc.subjectGroup Theory
dc.subject05C10, 05C12, 20F06, 57M15
dc.titleThe absence of efficient dual pairs of spanning trees in planar graphs
dc.typetext

Files

Collections

arXiv