Sphere and dot product representations of graphs

A graph $G$ is a $k$-sphere graph if there are $k$-dimensional real vectors $v_1,\dots,v_n$ such that $ij\in 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,\dots,v_n$ such that $ij\in 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).