Complexity of Some Geometric and Topological Problems
Schaefer, Marcus (2010) Complexity of Some Geometric and Topological Problems. In: Graph Drawing 17th International Symposium, GD 2009, September 22-25, 2009, Chicago, IL, USA , pp. 334-344 (Official URL: http://dx.doi.org/10.1007/978-3-642-11805-0_32).
Full text not available from this repository.
We show that recognizing intersection graphs of convex sets has the same complexity as deciding truth in the existential theory of the reals. Comparing this to similar results on the rectilinear crossing number and intersection graphs of line segments, we argue that there is a need to recognize this level of complexity as its own class.
Repository Staff Only: item control page