Bipartite Embeddings of Trees in the Plane

Abellanas, Manuel and Garcìa, J. and Hernández, Gregorio and Noy, M. and Ramos, Pedro (1997) Bipartite Embeddings of Trees in the Plane. In: Symposium on Graph Drawing, GD '96, September 18-20, 1996, Berkeley, California, USA , pp. 1-10 (Official URL:

Full text not available from this repository.


Given a tree T on n vertices and a set P of n points in the plane in general position, it is known that T can be straight line embedded in P without crossings. Now imagine the set P is partitioned into two disjoint subsets R and B, and we ask for an embedding of T in P without crossings and with the property that all edges join a point in R (red) and a point in B (blue). In this case we say that T admits a bipartite embedding with respect to the bipartition (R,B). Examples show that the problem in its full generality is not solvable. In view of this fact we consider several embedding problems and study for which bipartitions they can be solved. We present several results that are valid for any bipartition (R,B) in general position, and some other results that hold for particular configurations of points.

Item Type:Conference Paper
Additional Information:10.1007/3-540-62495-3_33
Classifications:G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.420 Crossings
M Methods > M.900 Tree
ID Code:92

Repository Staff Only: item control page


J. Akiyama and J. Urrutia, Simple Alternating Path Problems, Discrete Mathematics 84 (1990), pp. 101-103.

P. Bose, M. McAllister and J. Snoeyink, Optimal Algorithms to Embed Trees in the Plane, in Proc. Graph Drawing 95, Springer Verlag LNCS Vol. 1027, pp.64-75.

H. Edelsbrunner, Algorithms in Combinatorial Geometry, Spriner Verlag (Berlin, 1987).

A. García and J. Tejel, Dividiendo una nube de puntos en regiones convexas, Actas VI Encuentros de Geometría Computacional, pp. 169-174, 1995.

Y. Ikebe, M. Perles, A, Tamura and S. Tokunaga, The Rooted Tree Embedding Problem into Points in the Plane, Discrete and Computational Geometry 11 (1994), pp.51-63.

J. Pach and J. Töröcsik, Layout of Roodet trees, in Planar Graphs (W.T. Trotter, ed.), DIMACS Series, Vol. 9, Amer. Math. Soc., pp. 131-137.

A. Tamura and Y. Tamura, Degree Constrained Tree Embedding Into Points in the Plane, Information Proc. Letters 44 (1992), pp. 211-214.