Orthogeodesic PointSet Embedding of TreesDi Giacomo, Emilio and Frati, Fabrizio and Fulek, Radoslav and Grilli, Luca and Krug, Marcus (2012) Orthogeodesic PointSet Embedding of Trees. In: Graph Drawing 19th International Symposium, GD 2011, September 2123, 2011 , pp. 5263(Official URL: http://dx.doi.org/ 10.1007/9783642258787_6). Full text not available from this repository.
Official URL: http://dx.doi.org/ 10.1007/9783642258787_6
AbstractLet S be a set of N grid points in the plane, and let G a graph with n vertices (n ≤ N ). An orthogeodesic pointset 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 nvertex tree in F admits an orthogeodesic pointset embedding on every gridpoint set of size f (n)? We provide polynomial upper bounds on f (n) for both planar and nonplanar orthogeodesic pointset embeddings as well as for the case when edges are required to be Lshaped chains.
Actions (login required)
