The Real Logic of Drawing Graphs

Speaker

Marcus Schaefer
DePaul University
http://ovid.cs.depaul.edu/

Description

We study the complexity of several geometric graph drawing problems, including the recognition problem for intersection graphs of convex sets and the realizability and rigidity of linkages. It turns out that the complexity of these problems is the same as deciding truth in the existential theory of the real numbers. Computationally this implies that these problems are hard (NP-hard), but algorithmically solvable (in polynomial space); numerically, this means that exponential precision is required for actual realizations.We compare this to known results in the literature, including results on the rectilinear crossing number, the Steinitz problem, and Nash equilibria, and argue that there is a need to introduce and study new classes to capture this type of complexity.