Search

A greedily routable region (GRR) is a closed subset of , in which any destination point can be reached from any starting point by always moving in the direction with maximum reduction of the distance to the destination in each point of the path. Recently, Tan and Kermarrec proposed a geographic routing protocol for dense wireless sensor networks based on decomposing the network area into a small number of interior-disjoint GRRs. They showed that minimum decomposition is NP-hard for polygonal regions with holes. We consider minimum GRR decomposition for plane straight-line drawings of graphs. Here, GRRs coincide with self-approaching drawings of trees, a drawing style which has become a popular research topic in graph drawing. We show that minimum decomposition is still NP-hard for graphs with cycles and even for trees, but can be solved optimally for trees in polynomial time, if we allow only certain types of GRR contacts. Additionally, we give a 2-approximation for simple polygons, if a given triangulation has to be respected. [ABSTRACT FROM AUTHOR]

Deciding 3-colorability for general plane graphs is known to be an NP-complete problem. However, for certain families of graphs, like triangulations, polynomial time algorithms exist. We consider the family of pseudo-triangulations, which are a generalization of triangulations, and prove NP-completeness for this class. This result also holds if we bound their face degree to four, or exclusively consider pointed pseudo-triangulations with maximum face degree five. In contrast to these completeness results, we show that pointed pseudo-triangulations with maximum face degree four are always 3-colorable. An according 3-coloring can be found in linear time. Some complexity results relating to the rank of pseudo-triangulations are also given. [ABSTRACT FROM AUTHOR]

In this paper we consider the ip operation for combinatorial pointed pseudotriangulations where faces have size 3 or 4, so-called combinatorial 4-PPTs.We show that every combinatorial 4-PPT is stretchable to a geometric pseudo-triangulation, which in general is not the case if faces may have size larger than 4. Moreover, we prove that the ip graph of combinatorial 4-PPTs is connected and has diameter O( n2), even in the case of labeled vertices with fixed outer face. For this case we provide an Ω(n log n) lower bound. [ABSTRACT FROM AUTHOR]

This paper deals with the fast computation of straight skeletons of planar straight-line graphs (PSLGs) at an industrial-strength level. We discuss both the theoretical foun-dations of our algorithm and the engineering aspects of our implementation BONE. Our investigation starts with an analysis of the triangulation-based algorithm by Aichholzer and Aurenhammer and we prove the existence of flip-event-free Steiner triangulations. This result motivates a careful generalization of motorcycle graphs such that their inti-mate geometric connection to straight skeletons is maintained. Based on the generalized motorcycle graph, we devise a non-procedural characterization of straight skeletons of PSLGs and we discuss how to obtain a discretized version of a straight skeleton by means of graphics rendering. Most importantly, this generalization allows us to present a fast and easy-to-implement straight-skeleton algorithm. We implemented our algorithm in C++ based on floating-point arithmetic. Extensive benchmarks with our code BONE demonstrate an 0(n log N) time complexity and 0(n) memory footprint on 22 300 datasets of diverse characteristics. This is a linear factor better than the implementation provided by CGAL 4.0, which shows an 0(n² logn) time complexity and an 0(n²) memory footprint; the CGAL code has been the only fully-functional straight-skeleton code so far. In particular, on datasets with ten thousand vertices, BONE requires about 0.2-0.6 seconds instead of 4-7 minutes consumed by the CGAL code, and BONE uses only 20 MB heap memory instead of several gigabytes. We conclude our paper with a discussion of the engineering aspects and principles that make BONE reliable enough to compute the straight skeleton of datasets comprising a few million vertices on a desktop computer. [ABSTRACT FROM AUTHOR]

Given a set P of n points in the plane, the order-k Delaunay graph is a graph with vertex set P and an edge exists between two points p, q ∈ P when there is a circle through p and q with at most k other points of P in its interior. We provide upper and lower bounds on the number of edges in an order-k Delaunay graph. We study the combinatorial structure of the set of triangulations that can be constructed with edges of this graph. Furthermore, we show that the order-k Delaunay graph is connected under the flip operation when k ≤ 1 but not necessarily connected for other values of k. If P is in convex position then the order-k Delaunay graph is connected for all k ≥ 0. We show that the order-k Gabriel graph, a subgraph of the order-k Delaunay graph, is Hamiltonian for k ≥ 15. Finally, the order-k Delaunay graph can be used to efficiently solve a coloring problem with applications to frequency assignments in cellular networks. [ABSTRACT FROM AUTHOR]