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

##### MSC:
 05C05 Trees
##### Keywords:
planar graphs; geometric graph; plane spanning tree