Gabriel Triangulations and Angle-Monotone Graphs: Local Routing and Recognition

DOI10.1007/978-3-319-50106-2_40zbMath1471.68289arXiv1608.08892OpenAlexW2512795172MaRDI QIDQ2961543

Prosenjit Bose, Nicolas Bonichon, Paz Carmi, Anna Lubiw, Sander Verdonschot, Irina Kostitsyna

Publication date: 21 February 2017

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1608.08892

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (11)

On the plane angle-monotone graphs ⋮ Angle-monotonicity of Delaunay triangulation ⋮ Rooted Uniform Monotone Minimum Spanning Trees ⋮ On the spanning and routing ratios of the directed \(\varTheta_6\)-graph ⋮ Local routing in sparse and lightweight geometric graphs ⋮ On the spanning and routing ratios of the directed \(\Theta_6\)-graph ⋮ Emanation graph: a plane geometric spanner with Steiner points ⋮ On the area requirements of planar greedy drawings of triconnected planar graphs ⋮ On planar greedy drawings of 3-connected planar graphs ⋮ Drawing graphs as spanners ⋮ Edge-Unfolding Nearly Flat Convex Caps

Cites Work

• Monotone drawings of graphs with few directions
• Some results on greedy embeddings in metric spaces
• Provably good mesh generation
• There are planar graphs almost as good as the complete graph
• On a conjecture related to geometric routing
• The Stretch Factor of the Delaunay Triangulation Is Less than 1.998
• Connections between Theta-Graphs, Delaunay Triangulations, and Orthogonal Surfaces
• Geometric Spanner Networks
• Optimal Local Routing on Delaunay Triangulations Defined by Empty Equilateral Triangles
• Upper and Lower Bounds for Online Routing on Delaunay Triangulations
• Monotone Drawings of 3-Connected Plane Graphs
• Self-approaching curves
• Curves with increasing chords
• Self-approaching Graphs
• Lower Bounds on the Dilation of Plane Spanners
• Monotone Drawings of Graphs
• An Algorithm to Construct Greedy Drawings of Triangulations
• Increasing-Chord Graphs On Point Sets
• Generalized self-approaching curves

This page was built for publication: Gabriel Triangulations and Angle-Monotone Graphs: Local Routing and Recognition