Orthogeodesic point-set embedding of trees (Q2391540)

From MaRDI portal
Revision as of 23:33, 3 August 2023 by Importer (talk | contribs) (‎Created a new Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
Orthogeodesic point-set embedding of trees
scientific article

    Statements

    Orthogeodesic point-set embedding of trees (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    31 July 2013
    0 references
    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).
    0 references
    graph drawing
    0 references
    orthogonal drawing
    0 references
    tree
    0 references
    orthogeodesic point-set embedding
    0 references
    Manhattan distance
    0 references
    caterpillar
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references