zbMATH — the first resource for mathematics

The rooted tree embedding problem into points in the plane. (English) Zbl 0791.05027
Let \(T\) be a rooted tree with \(n\) vertices and \(N\) a set \(\{p_ 1,\dots,p_ n\}\) of \(n\) points in general position in \(\mathbb{R}^ 2\). Denote the sets of vertices and edges of \(T\) by \(V(T)\) and \(E(T)\), respectively. A bijection \(\varphi\) from \(V(T)\) to \(N\) satisfying the conditions:
(C1) \(\varphi(r_ 1)=p_ 1\) \((r_ 1\) is the root of \(T)\),
(C2) for nonadjacent edges \(u_ 1v_ 1\), \(u_ 2v_ 2 \in E(T)\), the line segments \(\overline {\varphi (u_ 1) \varphi(v_ 1)}\), \(\overline {\varphi (u_ 2) \varphi (v_ 2)}\) are disjoint,
is called a rooted tree embedding (or \(rt\)-embedding).
The main theorem states that an \(rt\)-embedding of \(V(T)\) on \(N\) always exists and that some \(rt\)-embedding can be constructed in polynomial time with respect to \(n\).

05C10 Planar graphs; geometric and topological aspects of graph theory
05C05 Trees
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
Full Text: DOI EuDML
[1] Edelsbrunner, H. (1987),Algorithms in Combinatorial Geometry, Springer-Verlag, Berlin.
[2] Pach, J.; Töröcsik, J.; Trotter, W. T. (ed.), Layout of rooted trees, 131-137, (1993), Providence, RI · Zbl 0792.05083
[3] Perles, M. (1990), Open problem proposed at the DIMACS Workshop on Arrangements, Rutgers University.
[4] Preparata, F. P., and Shamos, L. I. (1985),Computational Geometry—An Introduction, Springer-Verlag, New York. · Zbl 0759.68037
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.