Orthogeodesic point-set embedding of trees

DOI10.1016/j.comgeo.2013.04.003zbMath1279.65027MaRDI QIDQ2391540

Emilio Di Giacomo, Luca Grilli, Fabrizio Frati, Radoslav Fulek, Marcus Krug

Publication date: 31 July 2013

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0925772113000369

zbMATH Keywords

tree; graph drawing; caterpillar; orthogonal drawing; Manhattan distance; orthogeodesic point-set embedding

Mathematics Subject Classification ID

05C05: Trees

68R10: Graph theory (including graph drawing) in computer science

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

65D18: Numerical aspects of computer graphics, image analysis, and computational geometry

Related Items

Improved Bounds for Drawing Trees on Fixed Points with L-Shaped Edges, Ordered Level Planarity, Geodesic Planarity and Bi-Monotonicity, On L-shaped point set embeddings of trees: first non-embeddable examples, Rollercoasters and Caterpillars, -shaped point set embeddings of high-degree plane graphs, Rollercoasters: Long Sequences without Short Runs, On L-shaped point set embeddings of trees: first non-embeddable examples, Orthogeodesic Point-Set Embedding of Trees

Cites Work

• Unnamed Item
• Unnamed Item
• How to draw a planar graph on a grid
• Universal sets of \(n\) points for one-bend drawings of planar graphs with \(n\) vertices
• Drawing colored graphs on colored points
• Drawing colored graphs with constrained vertex positions and few bends per edge
• Theoretical results on at most 1-bend embeddability of graphs
• A better heuristic for orthogonal graph drawings
• On embedding an outer-planar graph in a point set
• Drawing planar graphs using the canonical ordering
• Hamiltonian orthogeodesic alternating paths
• On the Computational Complexity of Upward and Rectilinear Planarity Testing
• Orthogonal Graph Drawing with Flexibility Constraints
• Orthogeodesic Point-Set Embedding of Trees
• Manhattan-Geodesic Embedding of Planar Graphs
• On Embedding a Graph in the Grid with the Minimum Number of Bends
• Universality considerations in VLSI circuits
• Optimal Algorithms to Embed Trees in a Point Set
• Embedding Vertices at Points: Few Bends Suffice for Planar Graphs
• Drawing Planar Graphs on Area
• Planar embeddability of the vertices of a graph using a fixed point set is NP-hard
• Drawing Graphs with Vertices at Specified Positions and Crossings at Large Angles