Advertisement
Published in:
2016 | OriginalPaper | Chapter
Gabriel Triangulations and Angle-Monotone Graphs: Local Routing and Recognition
Authors : Nicolas Bonichon, Prosenjit Bose, Paz Carmi, Irina Kostitsyna, Anna Lubiw, Sander Verdonschot
Published in: Graph Drawing and Network Visualization
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
A geometric graph is angle-monotone if every pair of vertices has a path between them that—after some rotation—is x- and y-monotone. Angle-monotone graphs are \(\sqrt{2}\)-spanners and they are increasing-chord graphs. Dehkordi, Frati, and Gudmundsson introduced angle-monotone graphs in 2014 and proved that Gabriel triangulations are angle-monotone graphs. We give a polynomial time algorithm to recognize angle-monotone geometric graphs. We prove that every point set has a plane geometric graph that is generalized angle-monotone—specifically, we prove that the half-\(\theta _6\)-graph is generalized angle-monotone. We give a local routing algorithm for Gabriel triangulations that finds a path from any vertex s to any vertex t whose length is within \(1 + \sqrt{2}\) times the Euclidean distance from s to t. Finally, we prove some lower bounds and limits on local routing algorithms on Gabriel triangulations.