Graph Drawing 2004: Conference report...

I have noted in the past that graph drawing is an interesting area on the boundary of geometry, combinatorics, graph theory, and visualization. This year's graph drawing conference was held in Harlem at the City College from Sep 29 to Oct 2, and Yehuda Koren was kind enough to submit a conference report. Here it is, with minor edits:

---

Graph Drawing 2004 was held on Sept. 29-Oct. 2, in City College, NY.

More than 50 full papers were presented, dealing with all aspects of drawing graphs/digraphs. These include works ranging from pure graph-theory to design of user interfaces, and geometry-related papers along with heuristics for graph embedding and much more.

The invited speakers were Paul Seymour from Princeton University who spoke on "The Structure of Claw-Free Graphs", and Erik Demaine from M. I. T. on "Fast Algorithms for Hard Graph Problems: Bidimensionality, Minors, and Local Treewidth" (ed: Erik and Mohammed Taghi Hajiaghayi have two papers on this topic in SODA 2005)

As usual some talks were more interesting, some less, and some I missed. To get some impression for those of you that somehow missed this event; I want to mention here three works with a strong geometry motivation.

1. "Partitions of Complete Geometric Graphs into Plane Trees" by P. Bose, F. Hurtado, E. Rivera-Campo and D.R. Wood.

They deal with a known open problem: "Does every complete geometric graph with an even number of vertices have a partition of its edge set into plane spanning trees?"

A geometric graph is one in which the vertices are a set of points in the plane in general position (ed: amen)(that is, no three are collinear) and edges are closed segments connecting the points. Plane spanning trees contain all n vertices of original graph and no two edges intersect.

Of course, for a complete graph with n vertices we have n(n-1)/2 edges, so the partition must be into n/2 spanning trees. The answer is known to be affirmative for convex complete graphs (where convex means that the vertices are in convex position), so what left for the authors in this case is to characterize all such partitioning for convex complete graph, which is pretty nice.

The authors also show the existence of such partitioning for a broader family of graphs. And for desert they show that when the graphs are not necessarily spanning (and then we may partition into more than n/2 trees), an upper bound for the number of trees would be n-\sqrt(n/12).

2. "Reconfiguring Triangulations with Edge Flips and Point Moves", by G. Aloupis, P. Bose and P. Morin

The authors deal with transformations between different triangulations. They show that O(nlogn) edge-flips and point moves can transform any geometric near-triangulation on n-points to any other near-triangulation on n (different) points. Thus, they improve a previous O(n²) bound. They also suggest a more general point move that further reduces the complexity to O(n).


3. "No-three-in-line-in-3D" by A. Por and D. Wood.

Their work is based on Erdös' proof in 1951 (of a problem proposed by Dudeney in 1917) that one can place O(n) points in nxn grid with no three points are collinear.

The authors prove a smooth generalization to 3-D: One can place O(n²) point in an nxnxn grid where no three are collinear. They also consider additional generalizations more relevant to graph drawing.