Gabriel Triangulations and Angle-Monotone Graphs: Local Routing and Recognition
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 in
- PDF / 446,270 Bytes
- 13 Pages / 439.37 x 666.142 pts Page_size
- 103 Downloads / 190 Views
6
LaBRI, University of Bordeaux, Bordeaux, France [email protected] 2 School of Computer Science, Carleton University, Ottawa, Canada [email protected] 3 Department of Computer Science, Ben-Gurion University of the Negev, Beersheba, Israel [email protected] 4 Universit´e Libre de Bruxelles, Brussels, Belgium [email protected] 5 David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, Canada [email protected] School of Electrical Engineering and Computer Science, University of Ottawa, Ottawa, Canada [email protected]
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 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 anglemonotone—specifically, we prove that the half-θ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 + 2 times the Euclidean distance from s to t. Finally, we prove some lower bounds and limits on local routing algorithms on Gabriel triangulations.
1
Introduction
A geometric graph has vertices that are points in the plane, and edges that are drawn as straight-line segments, with the weight of an edge being its Euclidean length. A geometric graph need not be planar. Geometric graphs that have relatively short paths are relevant in many applications for routing and network design, and have been a subject of intense research. A main scenario is that we c Springer International Publishing AG 2016 Y. Hu and M. N¨ ollenburg (Eds.): GD 2016, LNCS 9801, pp. 519–531, 2016. DOI: 10.1007/978-3-319-50106-2 40
520
N. Bonichon et al.
are given a point set and must construct a sparse geometric graph on that point set with good shortest path properties. If the shortest path between every pair of points has length at most t times the Euclidean distance between the points, then the geometric graph is called a t-spanner, and the minimum such t is called the spanning ratio. Since their introduction by Paul Chew in 1986 [10], spanners have been heavily studied [18]. Besides the existence of short paths, another issue is routing—how to find short paths in a geometric graph. One goal is to find paths using local routing where the path is found one vertex at a time using only local information about the neighbours of the current vertex plus the coordinates of the destination. A main example of such a method is greedy routing: from the current vertex u take any edge to a vertex v that is closer (in Euclidean distance) to the destination than u is. The geometric graphs for which greedy routing succeeds in finding a path are called greedy drawi
Data Loading...
