Sphere and Dot Product Representations of Graphs
Tóm tắt
A graph G is a k-sphere graph if there are k-dimensional real vectors v
1,…,v
n
such that ij∈E(G) if and only if the distance between v
i
and v
j
is at most 1. A graph G is a k-dot product graph if there are k-dimensional real vectors v
1,…,v
n
such that ij∈E(G) if and only if the dot product of v
i
and v
j
is at least 1. By relating these two geometric graph constructions to oriented k-hyperplane arrangements, we prove that the problems of deciding, given a graph G, whether G is a k-sphere or a k-dot product graph are NP-hard for all k>1. In the former case, this proves a conjecture of Breu and Kirkpatrick (Comput. Geom. 9:3–24, 1998). In the latter, this answers a question of Fiduccia et al. (Discrete Math. 181:113–138, 1998). Furthermore, motivated by the question of whether these two recognition problems are in NP, as well as by the implicit graph conjecture, we demonstrate that, for all k>1, there exist k-sphere graphs and k-dot product graphs such that each representation in k-dimensional real vectors needs at least an exponential number of bits to be stored in the memory of a computer. On the other hand, we show that exponentially many bits are always enough. This resolves a question of Spinrad (Efficient Graph Representations, 2003).
Tài liệu tham khảo
Basu, S., Pollack, R., Roy, M.-F.: On the combinatorial and algebraic complexity of quantifier elimination. J. ACM 43(6), 1002–1045 (1996)
Basu, S., Pollack, R., Roy, M.-F.: Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics, 2nd edn. Springer, Berlin (2006)
Björner, A., Las Vergnas, M., Sturmfels, B., White, N., Ziegler, G.M.: Oriented Matroids. Encyclopedia of Mathematics and Its Applications, vol. 46, 2nd edn. Cambridge University Press, Cambridge (1999)
Breu, H., Kirkpatrick, D.G.: Unit disk graph recognition is NP-hard. Comput. Geom. 9(1–2), 3–24 (1998)
Felsner, S.: In: Geometric Graphs and Arrangements. Advanced Lectures in Mathematics. Friedr. Vieweg, Wiesbaden (2004). Some chapters from combinatorial geometry
Fiduccia, C.M., Scheinerman, E.R., Trenk, A., Zito, J.S.: Dot product representations of graphs. Discrete Math. 181(1–3), 113–138 (1998)
Havel, T.F.: The combinatorial distance geometry approach to the calculation of molecular conformation. Ph.D. thesis, University of California, Berkeley (1982)
Kannan, S., Naor, M., Rudich, S.: Implicit representation of graphs. SIAM J. Discrete Math. 5(4), 596–603 (1992)
Looges, P.J., Olariu, S.: Optimal greedy algorithms for indifference graphs. Comput. Math. Appl. 25(7), 15–25 (1993)
Maehara, H.: Space graphs and sphericity. Discrete Appl. Math. 7(1), 55–64 (1984)
Mahadev, N.V.R., Peled, U.N.: Threshold Graphs and Related Topics. Annals of Discrete Mathematics, vol. 56. North-Holland, Amsterdam (1995)
McDiarmid, C.J.H., Müller, T.: Integer representation of disk and segment graphs (2011, submitted). arXiv: 1111.2931
McDiarmid, C.J.H., Müller, T.: The number of bits needed to represent a unit disk graph. In: Proceedings of 36th International Workshop on Graph Theoretic Concepts in Computer Science (WG 2010). Lecture Notes in Computer Science, vol. 6410, pp. 315–323 (2010)
Mnëv, N.E.: Realizability of combinatorial types of convex polyhedra over fields. J. Sov. Math. 28, 606–609 (1985) (in Russian)
Mnëv, 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)
Reiterman, J., Rödl, V., Šiňajová, E.: Embeddings of graphs in Euclidean spaces. Discrete Comput. Geom. 4(4), 349–364 (1989)
Reiterman, J., Rödl, V., Šiňajová, E.: Geometrical embeddings of graphs. Discrete Math. 74(3), 291–319 (1989)
Reiterman, J., Rödl, V., Šiňajová, E.: On embedding of graphs into Euclidean spaces of small dimension. J. Comb. Theory, Ser. B 56(1), 1–8 (1992)
Schaefer, M.: Complexity of some geometric and topological problems. In: Graph Drawing, 17th International Symposium (GD 2009), Chicago, 22–25 September 2009. Lecture Notes in Computer Science, vol. 5849, pp. 334–344 (2010)
Schrijver, A.: Theory of Linear and Integer Programming. Wiley-Interscience Series in Discrete Mathematics. Wiley, Chichester (1986)
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. Am. Math. Soc., Providence (1991)
Spinrad, J.P.: Efficient Graph Representations. Fields Institute Monographs, vol. 19. Am. Math. Soc., Providence (2003)