Seminar • Algorithms and Complexity — The Complexity of Graph Drawings and Representations

Wednesday, October 10, 2018 1:30 pm - 1:30 pm EDT (GMT -04:00)

Anna Lubiw
David R. Cheriton School of Computer Science

In this talk I will look at geometric graph representations from the perspective of three issues: the algorithmic complexity of finding a representation; the bit complexity of the representation; and whether there is a morph between any two combinatorially equivalent representations.

The case of straight-line drawings of planar graphs is nice for all three issues: every planar graph has such a representation; the bit complexity is log n since vertices can be placed on an nxn grid; and morphs always exist. 

By contrast, recognizing intersection graphs of unit discs is hard for existential theory of the reals; coordinates may require an exponential number of bits; and morphs are not always possible. These negative results are related.

I will show a version of straight-line planar drawing that lies on the “hard” end of this spectrum. It is the problem of drawing a planar graph with straight-line edges inside a given polygonal region, when some vertices are fixed on the boundary of the region. In other words, the extension of Tutte’s graph drawing algorithm when his convex outer boundary is generalized to a polygonal region.

Joint work with Tillmann Miltzow and Debajyoti Mondal.