Dissertation/Thesis Abstract

Geometric graph theory and wireless sensor networks
by Sarioz, Deniz, Ph.D., City University of New York, 2012, 113; 3499283
Abstract (Summary)

In this work, we apply geometric and combinatorial methods to explore a variety of problems motivated by wireless sensor networks. Imagine sensors capable of communicating along straight lines except through obstacles like buildings or barriers, such that the communication network topology of the sensors is their visibility graph. Using a standard distributed algorithm, the sensors can build common knowledge of their network topology.

We first study the following inverse visibility problem: What positions of sensors and obstacles define the computed visibility graph, with fewest obstacles? This is the problem of finding a minimum obstacle representation of a graph. This minimum number is the obstacle number of the graph. Using tools from extremal graph theory and discrete geometry, we obtain for every constant h that the number of n-vertex graphs that admit representations with h obstacles is [special characters omitted]. We improve this bound to show that graphs requiring Ω( n/log2n) obstacles exist.

We also study restrictions to convex obstacles, and to obstacles that are line segments. For example, we show that every outerplanar graph admits a representation with five convex obstacles, and that allowing obstacles to intersect sometimes decreases their required number.

Finally, we study the corresponding problem for sensors equipped with GPS. Positional information allows sensors to establish common knowledge of their communication network geometry, hence we wish to compute a minimum obstacle representation of a given straight-line graph drawing. We prove that this problem is NP-complete, and provide a O(log OPT)-factor approximation algorithm by showing that the corresponding hypergraph family has bounded Vapnik-Chervonenkis dimension.

Indexing (document details)
Advisor: Pach, Janos
Commitee: Aronov, Boris, Bar-Noy, Amotz, Khan, Bilal
School: City University of New York
Department: Computer Science
School Location: United States -- New York
Source: DAI-B 73/07(E), Dissertation Abstracts International
Source Type: DISSERTATION
Subjects: Applied Mathematics, Computer science
Keywords: Approximation algorithms, Geometric graph theory, Geometric representations of graphs, Hypergraph transversals, Obstacle representations of graphs, Wireless sensor networks
Publication Number: 3499283
ISBN: 978-1-267-23588-6
Copyright © 2019 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy
ProQuest