Straight-line embeddings of two rooted trees in the plane
type: Item
instance of: scholarly article
title: Straight-line embeddings of two rooted trees in the plane
zbMATH Open document ID: 0934.05043
DOI: 10.1007/PL00009441
author: Mikio Kano
author: Atsushi Kaneko
published in: Discrete \& Computational Geometry
publication date: 2000-04-09T00:00:00Z
review text: Let \(T_1\) and \(T_2\) be two disjoint rooted trees of orders \(n_1\) and \(n_2\), with roots \(v_1\) and \(v_2\). Let \(P\) be a set of \(n_1+n_2\) points in the plane in a general position, containing two specified points \(p_1\) and \(p_2\). The authors prove that the union of \(T_1\) and \(T_2\) can be straight-line embedded in the plane onto \(P\) in such a way that \(v_i\) corresponds to \(p_i\) for \(i=1,2\). Moreover, an \(O(n^2\log{n})\) time algorithm is given for finding such an embedding, where \(n=n_1+n_2\).
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 1310078
zbMATH Keywords: rooted tree
zbMATH Keywords: straight-line embedding
reviewed by: Jozef Širáň
MaRDI profile type: Publication
Recommended article: Straight line embeddings of rooted star forests in the plane
Recommended article: Planar straight-line point-set embedding of trees with partial embeddings
Recommended article: Embeddings of binary trees in lines
Recommended article: Embedding of trees in Euclidean spaces
Recommended article: The rooted tree embedding problem into points in the plane
Recommended article: The geometry of plane linear trees
Recommended article: Planar straight-line realizations of 2-trees with prescribed edge lengths
Recommended article: Bipartite embeddings of trees in the plane
Recommended article: Grid straight-line embeddings of trees with a minimum number of bends per path
Recommended article: Plane Embeddings of 2-Trees and Biconnected Partial 2-Trees
description: scientific article; zbMATH DE number 1310078