Next: Problem 51: Linear-Volume 3D Grid Drawings of Planar Graphs
Previous: Problem 49: Planar Euclidean Maximum TSP
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.
Oswin Aichholzer, January 2003.
Settled negatively, January 2004.
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.
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.
triangulations; planar graphs
O. Aichholzer, 13 Aug. 2003; JOR, 15 Jan. 2004.
Owin Aichholzer, Clemens Huemer, and Hannes Krasser. Triangulations without pointed spanning trees. In Abstracts 20th European Workshop Comput. Geom., 2004.
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.