2012
Sphere and dot product representations of graphs
Publication
Publication
Discrete and Computational Geometry , Volume 47  Issue 3 p. 548 568
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 NPhard for all $k>1$. In the former case, this proves a conjecture of Breu and Kirkpatrick (Comput.~Geom.~9:324, 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).
Additional Metadata  

geometric representations of graphs, sphericity, dot product dimension  
Logistics (theme 3)  
Springer  
Discrete and Computational Geometry  
Organisation  Networks and Optimization 
Kang, R.J, & Müller, T. (2012). Sphere and dot product representations of graphs. Discrete and Computational Geometry, 47(3), 548–568.

See Also 

inProceedings

inProceedings

inProceedings
