Orthogeodesic Point-Set Embedding of Trees
Let S be a set of N grid points in the plane, no two of which lie on the same horizontal or vertical line, and let G be a graph with n vertices (n <= N). An orthogeodesic point-set embedding of G on S is a drawing of G such that each vertex is drawn as a point of S and each edge is a chain of horizontal and vertical segments with bends on grid points whose length is equal to the Manhattan distance of its end vertices. 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. (c) 2013 Elsevier B.V. All rights reserved.