Orthogeodesic point-set embedding of trees (Q2391540)

The paper deals with the problem of orthogeodesic point-set embedding of a graph on grid points. In this type of problem we have a graph \(G\), a grid \(S\) of \(N\) points, and we want to draw \(G\) in such a way 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 vertices. The authors study the problem from the combinatorial point of view, i.e., they characterize point sets that allow point-set embeddings of a whole class of graphs, and limit the class of graphs to trees. After some necessary definitions, the authors prove theorems (using inductive and constructive proofs) which provide a polynomial upper bound on the number of points of every \(k\)-spaced point set (a set of grid points is called \(k\)-spaced if the horizontal and vertical distance of any two points is at least \(k\)) that is universal for orthogeodesic point-set embeddings of different classes of trees using different drawing styles. In the theorems they take trees with vertices of maximum degree \(3\) and \(4\), and caterpillars (caterpillar is a tree such that by removing all leaves we are left with a path). The considered drawing styles are limited to planar and non-planar styles and also to more restricted \(L\)-shaped edges (an \(L\)-shaped edge is an orthogonal chain with only one bend).