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 , pp. 334-344(Official URL: http://dx.doi.org/10.1007/978-3-642-11805-0_32).

Full text not available from this repository.

Abstract

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.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-11805-0_32
Classifications: Z Theory > Z.999 Others
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1106

Actions (login required)

View Item View Item