BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
In 1968, Gallai conjectured that the edges of any connected graph with n vertices can be partitioned into ⌈2n⌉ paths. We show that this conjecture is true for every planar graph. More precisely, we show that every connected planar graph except K3 and K5− (K5 minus one edge) can be decomposed into ⌊2n⌋ paths.
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 angle-monotone---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.
Consider a weighted graph G where vertices are points in the plane and edges are line segments. The weight of each edge is the Euclidean distance between its two endpoints. A routing algorithm on G has a competitive ratio of c if the length of the path produced by the algorithm from any vertex s to any vertex t is at most c times the length of the shortest path from s to t in G. If the length of the path is at most c times the Euclidean distance from s to t, we say that the routing algorithm on G has a routing ratio of c.We present an online routing algorithm on the Delaunay triangulation with competitive and routing ratios of 5.90. This improves upon the best known algorithm that has competitive and routing ratio 15.48. The algorithm is a generalization of the deterministic 1-local routing algorithm by Chew on the L1-Delaunay triangulation. When a message follows the routing path produced by our algorithm, its header need only contain the coordinates of s and t. This is an improvement over the currently known competitive routing algorithms on the Delaunay triangulation, for which the header of a message must additionally contain partial sums of distances along the routing path.We also show that the routing ratio of any deterministic k-local algorithm is at least 1.70 for the Delaunay triangulation and 2.70 for the L1-Delaunay triangulation. In the case of the L1-Delaunay triangulation, this implies that even though there exists a path between two points x and y whose length is at most 2.61|[xy]| (where |[xy]| denotes the length of the line segment [xy]), it is not always possible to route a message along a path of length less than 2.70|[xy]|. From these bounds on the routing ratio, we derive lower bounds on the competitive ratio of 1.23 for Delaunay triangulations and 1.12 for L1-Delaunay triangulations.
Let E be the complete Euclidean graph on a set of points embedded in the plane. Given a constant t >= 1, a spanning subgraph G of E is said to be a t-spanner, or simply a spanner, if for any pair of vertices u,v in E the distance between u and v in G is at most t times their distance in E. A spanner is plane if its edges do not cross. This paper considers the question: "What is the smallest maximum degree that can always be achieved for a plane spanner of E?" Without the planarity constraint, it is known that the answer is 3 which is thus the best known lower bound on the degree of any plane spanner. With the planarity requirement, the best known upper bound on the maximum degree is 6, the last in a long sequence of results improving the upper bound. In this paper we show that the complete Euclidean graph always contains a plane spanner of maximum degree at most 4 and make a big step toward closing the question. Our construction leads to an efficient algorithm for obtaining the spanner from Chew's L1-Delaunay triangulation.
In this paper we determine the stretch factor of the L1-Delaunay and L∞-Delaunay triangulations, and we show that this stretch is 4+22≈2.61. Between any two points x,y of such triangulations, we construct a path whose length is no more than 4+22 times the Euclidean distance between x and y, and this bound is best possible. This definitively improves the 25-year old bound of 10 by Chew (SoCG '86). To the best of our knowledge, this is the first time the stretch factor of the well-studied Lp-Delaunay triangulations, for any real p≥1, is determined exactly.
A navigation on a set of points S is a rule for choosing which point to move to from the present point in order to progress toward a specified target. We study some navigations in the plane where S is a non uniform Poisson point process (in a finite domain) with intensity going to +∞. We show the convergence of the traveller path lengths, the number of stages done, and the geometry of the traveller trajectories, uniformly for all starting points and targets, for several navigations of geometric nature. Other costs are also considered. This leads to asymptotic results on the stretch factors of random Yao-graphs and random θ-graphs.
We present a simple bijection between Baxter permutations of size n and plane bipolar orientations with n edges. This bijection translates several classical parameters of permutations (number of ascents, right-to-left maxima, left-to-right minima...) into natural parameters of plane bipolar orientations (number of vertices, degree of the sink, degree of the source...), and has remarkable symmetry properties. By specializing it to Baxter permutations avoiding the pattern 2413, we obtain a bijection with non-separable planar maps. A further specialization yields a bijection between permutations avoiding 2413 and 3142 and series-parallel maps.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.