Let S be a set of N grid points in the plane, and let G 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 an orthogonal chain with bends on grid points whose length is equal to the Manhattan distance. We study the following problem. Given a family of trees F what is the minimum value f(n) such that every n-vertex tree in F admits an orthogeodesic point-set embedding on every grid-point set of size f(n)? 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 chains.
Orthogeodesic Point-Set Embedding of Trees
DI GIACOMO, Emilio;GRILLI, LUCA;
2012
Abstract
Let S be a set of N grid points in the plane, and let G 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 an orthogonal chain with bends on grid points whose length is equal to the Manhattan distance. We study the following problem. Given a family of trees F what is the minimum value f(n) such that every n-vertex tree in F admits an orthogeodesic point-set embedding on every grid-point set of size f(n)? 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 chains.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
