Project Description

Visibility Graphs of Simple Polygons:

Given a simple polygon P (i.e. P’s sides do not cross) in the plane, we can define the visibility graph of P, G(P), as follows: Let the vertices of G(P) correspond to the vertices of P and let two vertices in G(P) be connected by an edge, if and only if, those vertices “see” one another in P, i.e. the line segment connecting these vertices is either a side in P or else is contained inside P.

An example is found below:

Note: Visibility Graphs are only unique up to isomorphism.

The General Problem has two parts:

· Characterize Visibility Graphs of arbitrary simple polygons

· Find some way to efficiently recognize visibility graphs

These questions can be made more precise and there are many “subquestions” contained within them: e.g., given a graph that you know is the visibility graph of some simple polygon, reconstruct the polygon (this is known as the Reconstruction or Realizability Problem).

My Proposed Work:

To really understand my proposed project it would help to read the following reference:

Visibility Graphs of Staircase Polygons and The Weak Bruhat Order, Discrete and Computational Geometry, Vol. 14, No 3, 1995, pp. 331-358.

In this paper, James Abello , et. al, begin to develop a characterization of visibility graphs of staircase polygons, also called orthogonal convex fans. A picture is found below:

The characterization proceeds in many steps that create equivalences between these visibility graphs, a certain class of matrices called persistent matrices, and partial ordering of the symmetric group called the Weak Bruhat Order. (Note: An illustration of this partial ordering can be found on the index for this website). From these equivalences an algorithm is outlined that uses the Weak Bruhat Order as a guide to maneuver between persistent matrices creating a sequence that starts at the clique matrix, and ends at any inputted persistent matrix.

The question of realizablility is addressed in the sequel paper to the one above (in preprint). Unfortunately, while the first paper provides a nice algorithmic result (mainly that every persistent matrix is realizable as the skeleton of a balanced tableau (which is equivalent to a maximal chain in the Weak Bruhat Order)), the second one is not able to capitalize on this result to answer the question of realizability. Instead, the necessary staircase polygon is reconstructed directly from the persistent matrix, without making use of the large amount of machinery and equivalences formulated in the first paper.

One would like to offer an algorithmic solution to the question of realizability as well: namely, find some geometric realization of each step of the algorithm in the first paper. This would allow one to simultaneously reconstruct a staircase polygon from a persistent matrix. Further, evidence suggests that the techniques necessary for creating such a geometric realization would be generalizable to the larger problem of characterizing visibility graphs of arbitrary polygons.

Having said this, my proposed work for this summer is as follows:

1) Find an appropriate algorithmic solution that parallels the material in the first paper to the problem of reconstructing a staircase polygon given a persistent matrix.

2) Generalize the methods from 1 to address the problem of characterizing visibility graphs of arbitrary polygons.

Currently I have only begun to make progress on the first task. Namely, I have successfully proven that it is possible to simultaneous reconstruct a convex fan whose visibility graph has an adjacency matrix identical to a given persistent matrix by using a simplified version of the algorithm given in the first paper. As convex fans are more generalized version of staircase polygons, this would seem to suggest that using the algorithm in the first paper more appropriately would lead to a solution to 1).

I will include a sketch of the proof of the results I have on this website shortly.