Graph Drawing

The Graph Drawing deadline is fast approaching (May 31). It might seem strange to have an entire conference devoted to drawing graphs. However, this is a very valuable area; one would be surprised to see the number of situations in which one needs to visualize a large graph, and needs a good algorithm to do so.

There are many different approaches to drawing graphs; edges as straight lines or splines, or orthogonal chains, vertices as boxes or circles or points, faces as rectangles or orthogonal polygons. An interesting graph drawing result on planar graphs is Fary's theorem:

Any planar graph can be drawn with straight lines for edges and no crossings.

What makes the above result quite interesting is the following. Let a pseudoline arrangement be a collection of curves (each separating the plane into two parts) in which each pair intersects exactly once. Such a collection defines an arrangement of the plane (with faces, vertices and edges). Such an arrangement is stretchable if it is isomorphic to a straight line arrangement.

Not all pseudoline arrangements are stretchable. In fact, determining whether a given pseudoline arrangement is stretchable is NP-hard (due to Peter Shor).