next up previous
Next: Problem 51: Linear-Volume 3D Up: The Open Problems Project Previous: Problem 49: Planar Euclidean


Problem 50: Pointed Spanning Trees in Triangulations

Statement
Does every triangulation of a set of points in the plane (in general position) contain a pointed spanning tree as a subgraph? A vertex is pointed if one of its incident faces has an angle larger than π at this vertex. A spanning tree is pointed if all of its vertices are pointed.
Origin
Oswin Aichholzer, January 2003.
Status/Conjectures
Settled negatively, January 2004.
Partial and Related Results
Obviously true if a triangulation contains a Hamiltonian path or a pointed pseudotriangulation as a subgraph. For both structures there exist triangulations not containing them. (See, e.g., [O'R02a] for a discussion of pseudotriangulations.) Settled negatively by Aichholzer et al. [AHK04] with a 124-point counterexample. A consequence is that there are triangulations that require Ω(n) edge-flips to contain a pointed spanning tree, or to become Hamiltonian.
Related Open Problems
Problem 40.
Appearances
Posed by Oswin Aichholzer at the CCCG 2003 open-problem session, August 2003. Also posed by Bettina Speckmann as Problem 10 at the First Gremo Workshop on Open Problems in Stels, Switzerland, July 2003.
Categories
triangulations; planar graphs
Entry Revision History
O. Aichholzer, 13 Aug. 2003; JOR, 15 Jan. 2004.

Bibliography

AHK04
Owin Aichholzer, Clemens Huemer, and Hannes Krasser.
Triangulations without pointed spanning trees.
In Abstracts 20th European Workshop Comput. Geom., 2004.

O'R02a
J. O'Rourke.
Computational geometry column 43.
Internat. J. Comput. Geom. Appl., 12(3):263-265, 2002.
Also in SIGACT News, 33(1) Issue 122, Mar. 2002, 58-60.


next up previous
Next: Problem 51: Linear-Volume 3D Up: The Open Problems Project Previous: Problem 49: Planar Euclidean
The Open Problems Project - December 04, 2015