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.

Published in:
Proc. 19th International Symposium on Graph Drawing, 52-63
Presented at:
19th International Symposium on Graph Drawing, Eindhoven, Netherlands
Amsterdam, Elsevier Science Bv

 Record created 2011-12-19, last modified 2018-03-17

Rate this document:

Rate this document:
(Not yet reviewed)