We show that recognizing intersection graphs of convex sets has the same complexity as deciding truth in the existential first-order 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.
Schaefer, Marcus, "Complexity of Some Geometric Problems" (2008). Technical Reports. 9.
Technical Report Number