Computational And Combinatorial Problems On Some Geometric Proximity Graphs

Abstract

In this thesis, we focus on the study of computational and combinatorial problems on various geometric proximity graphs. Delaunay and Gabriel graphs are widely studied geometric proximity structures. These graphs have been extensively studied for their applications in wireless networks. Motivated by the applications in localized wireless routing, relaxed versions of these graphs known as Locally Delaunay Graphs (LDGs) and Locally Gabriel Graphs(LGGs) were proposed.

A geometric graph G=(V,E)is called a Locally Gabriel Graph if for every( u,v) ϵ E the disk with uv as diameter does not contain any neighbor of u or v in G. Thus, two edges (u, v) and(u, w)where u,v,w ϵ V conflict with each other if ∠uwv ≥ or ∠uvw≥π and cannot co-exist in an LGG. We propose another generalization of LGGs called Generalized locally Gabriel Graphs(GLGGs)in the context when certain edges are forbidden in the graph. For a given geometric graph G=(V,E), we define G′=(V,E′) as GLGG if G′is an LGG and E′⊆E. Unlike a Gabriel Graph ,there is no unique LGG or GLGG for a given point set because no edge is necessarily included or excluded. This property allows us to choose an LGG/GLGG that optimizes a parameter of interest in the graph. While Gabriel graphs are planar graphs, there exist LGGs with super linear number of edges. Also, there exist point sets where a Gabriel graph has dilation of Ω(√n)and there exist LGGs on the same point sets with dilation O(1). We study these graphs for various parameters like edge complexity(the maximum number of edges in these graphs),size of an independent set and dilation. We show that computing an edge maximum GLGG for a given problem instance is NP-hard and also APX-hard. We also show that computing an LGG on a given point set with minimum dilation is NP-hard. Then, we give an algorithm to verify whether a given geometric graph G=(V,E)is an LGG with running time O(ElogV+ V). We show that any LGG on n vertices has an independent set of size Ω(√nlogn). We show that there exists point sets with n points such that any LGG on it has dilation Ω(√n) that matches with the known upper bound. Then, we study some greedy heuristics to compute LGGs with experimental evaluation. Experimental evaluations for the points on a uniform grid and random point sets suggest that there exist LGGs with super-linear number of edges along with an independent set of near-linear size. Unit distance graphs(UDGs) are well studied geometric graphs. In this graph, an edge exists between two points if and only if the Euclidean distance between the points is unity. UDGs have been studied extensively for various properties most notably for their edge complexity and chromatic number. These graphs have also been studied for various special point sets most notably the case when the points are in convex position. Note that the UDGs form a sub class of the LGGs. UDGs/LGGs on convex point sets have O(nlogn) edges. The best known lower bound on the edge complexity of these graphs is 2n−7 when all the points are in convex position. A bipartite graph is called an ordered bipartite graph when the vertex set in each partition has a total order on its vertices. We introduce a family of ordered bipartite graphs with restrictions on some paths called path restricted ordered bi partite graphs (PRBGs)and show that their study is motivated by LGGs and UDGs on convex point sets. We show that a PRBG can be extracted from the UDGs/LGGs on convex point sets. First, we characterize a special kind of paths in PRBGs called forward paths, then we study some structural properties of these graphs. We show that a PRBG on n vertices has O(nlogn) edges and the bound is tight. It gives an alternate proof of O(nlogn)upper bound for the maximum number of edges in UDGs/LGGs on convex point sets. We study PRBGs with restrictions to the length of the forward paths and show an improved bound on the edge complexity when the length of the longest forward path is bounded. Then, we study the hierarchical structure amongst these graphs classes. Notably, we show that the class of UDGs on convex point sets is a strict sub class of LGGs on convex point sets.