The Open Problems Project

Next: Problem 51: Linear-Volume 3D Grid Drawings of Planar Graphs

Previous: Problem 49: Planar Euclidean Maximum TSP

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 \pi 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 \Omega(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.