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

**Previous:** Problem 49: Planar Euclidean Maximum TSP

- 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
- 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.

- [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.