Article ID Journal Published Year Pages File Type
10327391 Computational Geometry 2013 16 Pages PDF
Abstract
We study the following problem. Given a family F of trees, what is the minimum value f(n) such that every n-vertex tree in F admits an orthogeodesic point-set embedding on every set of grid points of size f(n) such that no two points lie on the same horizontal or vertical line? We provide polynomial upper bounds on f(n) for both planar and non-planar orthogeodesic point-set embeddings as well as for the case when edges are required to be L-shaped.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , , ,