Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10327391 | Computational Geometry | 2013 | 16 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Emilio Di Giacomo, Fabrizio Frati, Radoslav Fulek, Luca Grilli, Marcus Krug,