×

On the maximum degree of bipartite embeddings of trees in the plane. (English) Zbl 0959.05033

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, 166-171 (2000).
A geometric graph \(G=(V,E)\) is a graph drawn in the plane such that \(V\) is a set of points in the plane, no three of which are collinear, and \(E\) is a set of (possibly crossing) straight-line segments whose endpoints belong to \(V\). If \(G\) is a complete bipartite graph with partite sets \(A\), \(B\), then \(G\) is denoted by \(K(A,B)\). Let \(A\) and \(B\) be two disjoint sets of points in the plane such that \(|A|=|B|\) and no three points of \(A\cup B\) are collinear. The author shows that the geometric complete bipartite graph \(K(A,B)\) contains a spanning tree \(T\) without crossings, with maximum degree 3.
For the entire collection see [Zbl 0933.00046].

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
05C05 Trees
PDFBibTeX XMLCite