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.

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
ID Code:1106

Repository Staff Only: item control page

References

Bienstock, D.: Some provably hard crossing number problems. Discrete Comput. Geom. 6(5), 443–459 (1991)

Björner, A., Vergnas, M.L., Sturmfels, B., White, N., Ziegler, G.M.: Oriented matroids, 2nd edn. Encyclopedia of Mathematics and its Applications, vol. 46. Cambridge University Press, Cambridge (1999)

Bürgisser, P., Cucker, F.: Counting complexity classes for numeric computations. II. Algebraic and semialgebraic sets. J. Complexity 22(2), 147–191 (2006)

Canny, J.: Some algebraic and geometric computations in pspace. In: STOC 1988: Proceedings of the twentieth annual ACM symposium on Theory of computing, pp. 460–469. ACM, New York (1988)

Davis, E., Gotts, N.M., Cohn, A.G.: Constraint networks of topological relations and convexity. Constraints 4(3), 241–280 (1999)

Egenhofer, M.J.: Reasoning about binary topological relations. In: Günther, O., Schek, H.-J. (eds.) SSD 1991. LNCS, vol. 525, pp. 143–160. Springer, Heidelberg (1991)

Garey, M.R., Johnson, D.S.: Crossing number is NP-complete. SIAM Journal on Algebraic and Discrete Methods 4(3), 312–316 (1983)

Goodman, J.E., Pollack, R., Sturmfels, B.: Coordinate representation of order types requires exponential storage. In: STOC 1989: Proceedings of the twenty-first annual ACM symposium on Theory of computing, Seattle, Washington, United States, pp. 405–410. ACM, New York (1989)

Hlinený, P.: Crossing number is hard for cubic graphs. J. Combin. Theory Ser. B 96(4), 455–471 (2006)

Kratochvíl J.: Personal communication

Kratochvíl J., Matousek, J.: Intersection graphs of segments. J. Combin. Theory Ser. B 62(2), 289–315 (1994)

Kratochvíl J., Pergel, M.: Geometric intersection graphs: do short cycles help, (extended abstract). In: Lin, G. (ed.) COCOON 2007. LNCS, vol. 4598, pp. 118– 128. Springer, Heidelberg (2007)

Kyncl, J.: The complexity of several realizability problems for abstract topological graphs (unpublished manuscript) (based on Graph Drawing 2007 paper)

Mnev, N.E.: The universality theorems on the classification problem of configuration varieties and convex polytopes varieties. In: Topology and geometry—Rohlin Seminar. Lecture Notes in Math., vol. 1346, pp. 527–543. Springer, Berlin (1988)

Pach, J., Tóth, G.: Thirteen problems on crossing numbers. Geombinatorics 9(4), 194–207 (2000)

Pelsmajer, M.J., Schaefer, M., Stefankovic, D.: Crossing number of graphs with rotation systems. In: Hong, S.-H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol. 4875, pp. 3–12. Springer, Heidelberg (2008)

Renz, J.: Qualitative spatial reasoning with topological information. In: Renz, J. (ed.) Qualitative Spatial Reasoning with Topological Information. LNCS (LNAI), vol. 2293, p. 207. Springer, Heidelberg (2002)

Richter-Gebert, J.: Mnev’s universality theorem revisited. Sém. Lothar. Combin. 34 (1995) 19. Schaefer, M.: The real logic of drawing graphs (unpublished manuscript)

Schaefer, M., Sedgwick, E., Stefankovic, D.: Recognizing string graphs in NP. J. Comput. System Sci. 67(2), 365–380 (2003); Special issue on STOC 2002, Montreal, QC

Schaefer, M., Stefankovic, D.: Fixed points, nash equilibria, and the existential theory of the reals (unpublished manuscript)

Schaefer, M., Stefankovic, D.: Decidability of string graphs. J. Comput. System c Sci. 68(2), 319–334 (2004); Special issue on STOC 2001, Crete, Greece

Shor, P.W.: Stretchability of pseudolines is NP-hard. In: Applied geometry and discrete mathematics. DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 4, pp. 531–554. Amer. Math. Soc., Providence (1991)