Topic and Proposal
Visibility graphs are important tools that have many uses in computational geometry. For instance, they can be used for routing robots within polygons and for placing guards in art gallery problems. While easy to define (a graph on the vertices of a polygon, with edges if the vertices can see each other), there are many long-standing open problems on visibility graphs. We consider a brand new application of visibility graphs: graph drawing. We find the following questions, ordered by difficulty, particularly interesting:
- Can graph drawing methods such as force-directed drawing be used to reconstruct a polygon from its visibility graph?
- Given a graph and a polygon, can we draw the graph on the polygon to minimize differences with the visibility graph?
- Given a graph, can we find a polygon with a visibility graph that is similar to the graph?
Given that this is a new area of study, there are many other interesting open questions as well.
One of the main difficulties in working with visibility graphs is that it is unknown whether or not they can be recognized in polynomial time. We know that certain special classes of polygons can be recognized efficiently, and recognizing polygons with holes is NP-complete. Therefore, in this thesis, we prefer to concentrate on approximate algorithms. However, we are not opposed to investigating exact algorithms.
The work on the thesis will include:
- A literature search, focusing on existing graph drawing techniques and their possible application to visibility graphs. This entails reading and summarizing the state of the art.
- Choosing a research direction (e.g., force-directed drawing of visibility graphs) and making appropriate assumptions that make an algorithm more tractable.
- Developing open source software to implement essential building-block algorithms and new ideas.
- Running extensive experiments.
- And, of course, writing an extensive analysis in your thesis.
If you are interested in pushing the frontier of knowledge, and you are interested in learning more about essential graph drawing and geometric algorithms, then this is the thesis for you.
Obligatory: Excellent programming skills, Lectures Algorithms 1 and 2.
Desirable: Lectures “Computational Geometry” or “Algorithms for Visualizing Graphs.” We may make compromises for exceptional students.
Posted on January 4, 2016.