Next: Problem 51: LinearVolume 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
124point counterexample. A consequence is that there are
triangulations that require Ω(n) edgeflips to contain
a pointed spanning tree, or to become Hamiltonian.
 Related Open Problems
 Problem 40.
 Appearances
 Posed by Oswin Aichholzer at the CCCG 2003 openproblem 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.
 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):263265, 2002.
Also in SIGACT News, 33(1) Issue 122, Mar. 2002, 5860.
Next: Problem 51: LinearVolume 3D
Up: The Open Problems Project
Previous: Problem 49: Planar Euclidean
The Open Problems Project  September 19, 2017