×

zbMATH — the first resource for mathematics

Bipartite embeddings of trees in the plane. (English) Zbl 0929.05021
Summary: We consider the following embedding problem. A point set \(P\) in the plane in general position is partitioned into two disjoint sets \(R\) and \(B\), and we are asked to embed a tree \(T\) in \(P\) without crossings and with the additional property that all the edges connect a point in \(R\) to another point in \(B\). We study several problems related to such bipartite embeddings.

MSC:
05C10 Planar graphs; geometric and topological aspects of graph theory
05C05 Trees
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] M. Abellanas, J. Garcı́a, G. Hernandez, M. Noy, P. Ramos, Bipartite embeddings of trees in the plane, in: S. North (Ed.), Proc. of Graph Drawing 96, Lecture Notes in Computer Science, vol. 1190, Springer, Berlin, 1997, pp. 1-10.
[2] Akiyama, J.; Urrutia, J., Simple alternating path problem, Discrete math., 84, 101-103, (1990) · Zbl 0699.05032
[3] P. Bose, M. McAllister, J. Snoeyink, Optimal algorithms to embed trees in the plane, in: Proc. Graph Drawing 95, Lecture Notes in Computer Science, vol. 1027, Springer, Berlin, pp. 64-75. · Zbl 0890.05066
[4] H. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer, Berlin, 1987. · Zbl 0634.52001
[5] A. Garcı́a, J. Tejel, Dividiendo una nube de puntos en regiones convexas, in: Actas VI Encuentros de Geometrı́a Computacional, Barcelona, 1995, pp. 169-174.
[6] Hershberger, J.; Suri, S., Applications of a semi-dynamic convex hull algorithm, Bit, 32, 249-267, (1992) · Zbl 0761.68097
[7] Ikebe, Y.; Perles, M.; Tamura, A.; Tokunaga, S., The rooted tree embedding problem into points in the plane, Discrete comput. geom., 11, 51-63, (1994) · Zbl 0791.05027
[8] J. Pach, P.K. Aggarwal, Combinatorial Geometry, Wiley, New York, 1995.
[9] J. Pach, J. Töröcsik, Layout of rooted trees, in: W.T. Trotter (Ed.), Planar Graphs, DIMACS Series, vol. 9, Amer. Math. Soc., Providence, RI, 1993, pp. 131-137. · Zbl 0792.05083
[10] Tamura, A.; Tamura, Y., Degree constrained tree embedding into points in the plane, Inform. process. lett., 44, 211-214, (1992) · Zbl 0768.68184
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.