Orthogeodesic point-set embedding of trees
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).
- A better heuristic for orthogonal graph drawings
- Drawing colored graphs on colored points
- Drawing colored graphs with constrained vertex positions and few bends per edge
- Drawing graphs with vertices at specified positions and crossings at large angles
- Drawing planar graphs on \(\frac{8}{9}n^2\) area
- Drawing planar graphs using the canonical ordering
- Embedding Vertices at Points: Few Bends Suffice for Planar Graphs
- Hamiltonian orthogeodesic alternating paths
- How to draw a planar graph on a grid
- scientific article; zbMATH DE number 432759 (Why is no real title available?)
- scientific article; zbMATH DE number 3019031 (Why is no real title available?)
- Manhattan-geodesic embedding of planar graphs
- On Embedding a Graph in the Grid with the Minimum Number of Bends
- On embedding an outer-planar graph in a point set
- On the computational complexity of upward and rectilinear planarity testing
- Optimal Algorithms to Embed Trees in a Point Set
- Orthogeodesic point-set embedding of trees
- Orthogonal graph drawing with flexibility constraints
- Planar embeddability of the vertices of a graph using a fixed point set is NP-hard
- Theoretical results on at most 1-bend embeddability of graphs
- Universal sets of \(n\) points for one-bend drawings of planar graphs with \(n\) vertices
- Universality considerations in VLSI circuits
- On L-shaped point set embeddings of trees: first non-embeddable examples
- Orthogeodesic point-set embedding of trees
- Manhattan-geodesic embedding of planar graphs
- scientific article; zbMATH DE number 1080079 (Why is no real title available?)
- Improved bounds for drawing trees on fixed points with L-shaped edges
- Rollercoasters and caterpillars
- On L-shaped point set embeddings of trees: first non-embeddable examples
- L-shaped point set embeddings of high-degree plane graphs
- Rollercoasters: Long Sequences without Short Runs
- Recognizing Geometric Trees as Positively Weighted Straight Skeletons and Reconstructing Their Input
- Application of Bearing and Distance Trees to the Identification of Landmarks on the Coast
This page was built for publication: Orthogeodesic point-set embedding of trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2391540)
