Algorithms for Geometric Graphs - Tools, Techniques, Applications
German-Israeli Foundation for Scientific Research and Development (GIF)
In collaboration with
Developing algorithms and data structures for general graphs is a fundamental task any computer scientist must face. In some cases, considering a general graph can make the problem unnecessarily harder than it should be for a concrete application; often the real world imposes various restrictions on the input that may be exploited.
In this research proposal, we focus on several natural graph families that can be found in real world applications. More specifically, a common way to model wireless sensor networks is to represent each sensor as a point in the plane whose coverage area corresponds to a unit disk centered at it. An edge is added between two points if and only if their disks intersect. This model was suggested more than two decades ago by Clark, Colbourn, and Johnson. Nowadays, it is considered to be the classic model of wireless sensor networks. Nonetheless, despite its huge popularity, the unit disk model has some shortcomings in representing sensor networks. Two natural extensions that reflect wireless networks slightly better are the disk graph model and the directed disk graph model. The disk graph model allows for different radii, while the directed disk graph model lets us represent asymmetric communication.
In this project, we propose to investigate fundamental theoretical questions for these three graph families and to exploit their special structural properties to obtain better algorithms and data structures than those that are known (or even possible) for general graphs. Our research will be conducted in the following systematic approach: given a problem, we first investigate it on unit disk graphs. Then, if a satisfactory solution is obtained, we try to extend the results to disk graphs and to directed disk graphs. In preliminary work, we have already studied fundamental problems such as dynamic connectivity, spanner construction, routing schemes, and more. When trying to develop efficient algorithms and data structures for (directed) disk graphs, we face a whole new set of challenges that requires us to extend and refine existing tools from computational geometry to a new setting. We expect that these tools will be useful for various related models and problems. In the proposed project, we plan to extend and deepen our understanding of geometrically defined graphs, and to develop
general and widely applicable tools for dealing with them. In particular, our main goals are as follows:
• Design algorithms and data structures by conducting a systematic research of geometrically defined graphs that have rich structure which can be used to model real world data.
• Identify important parameters that characterize the “hardness” of geometric instances and develop algorithms that are parameterized using such parameters to obtain faster solutions for specific domains.
• Explore the relationship between geometrically defined graphs and general graphs.
• Develop new tools that can be used in black-box fashion to solve different problems in computational geometry.