zbMATH — the first resource for mathematics

A note on the existence of plane spanning trees of geometric graphs. (English) Zbl 0956.05030
Akiyama, Jin (ed.) et al., Discrete and computational geometry. Japanese conference, JCDCG ’98. Tokyo, Japan, December 9-12, 1998. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1763, 274-277 (2000).
Let \(P\) be a set of points in the plane. Every edge of a geometric graph \(G= (P,E)\) with point set \(P\) is a straight line with endpoints in \(P\). A plane spanning tree of \(G\) is a subtree of \(G\) that includes every vertex and has no edges whose lines cross in the plane. It is shown that every geometric graph \(G\) with at least \(5\) vertices has a plane spanning tree, when every induced subgraph of \(G\) with at least 5 vertices has a plane spanning tree.
For the entire collection see [Zbl 0933.00046].

05C05 Trees