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.

In this thesis the novel concept of Sycophant Wireless Sensors (SWS) is introduced. A SWS network is a static ectoparasitic clandestine sensor network mounted incognito on a mobile agent using only the agent&rsquo / s mobility without intervention. SWS networks not only communicate with each other through mobileWireless Sensor Networks (WSN) but also cooperate with them to form a global hybrid Wireless Sensor Network. Such a hybrid network has its own problems and opportunities, some of which have been studied in this thesis work. Assuming that direct position measurements are not always feasible tracking performance of the sycophant using range only measurements for various communication intervals is studied. Then this framework was used to create a hybrid 2D map of the environment utilizing the capabilities of the mobile network the sycophant. In order to show possible applications of a sycophant deployment, the sycophant sensor node was equipped with a laser ranger as its sensor, and it was let to create a 2D map of its environment. This 2D map, which corresponds to a height dierent than the follower network, was merged with the 2D map of the mobile network forming a novel rough 3D map. Then by giving up from the need to properly localize the sycophant even when it is disconnected to the rest of the network, a full 3D map of the environment is obtained by fusing 2D map and tracking capabilities of the mobile network with the 2D vertical scans of the environment by the sycophant. And finally connectivity problems that arise from the hybrid sensor/actuator network were solved. For this 2 new connectivity maintenance algorithms, one based on the helix structures of the proteins, and the other based on the acute triangulation of the space forming a Gabriel Graph, were introduced. In this new algorithms emphasis has been given to sparseness in order to increase fault tolerance to regional problems. To better asses sparseness a new measure, called Resistance was introduced, as well as another called updistance.