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.
Orthogeodesic point-set embedding of trees
DI GIACOMO, Emilio;GRILLI, LUCA;
2013
Abstract
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.