Kang and M¿ller, in this paper, prove two important positive results, and one partially negative result, on graph representation. A graph G=(V,E) consists of a set of vertices V, and a set of edges E. We can represent graphs in a variety of ways, but here, we are interested in two geometric representations: sphere and dot product representations.

A graph is a k-sphere graph if, whenever we associate k-dimensional real vectors to all vertices, the distance between any two such vectors is at most 1, if and only if the corresponding vertices form an edge in the graph. This representation originated in the early 1980s in the study of the geometry of molecules, and has also found applications in wireless networks. The authors prove that for all k>1, deciding that a given graph G is k-sphere is nondeterministic polynomial-time (NP)-hard, extending the state of the knowledge in a considerable way; the result was known for k=2 only.

Given a graph G as above with the association of k-dimensional vectors to the vertices, G is said to be a k-dot product graph whenever the dot product of two vectors is at least 1, if and only if the corresponding vertices form an edge. The second result by the authors shows that deciding whether a given graph is a k-dot product is also NP-hard for k>1 (for k=1, it was known to be solvable in linear time).

Finally, the authors show that as long as one uses bit string encoding for the vectors associated to the vertices of a k-sphere or a k-dot product graph, such vectors may need exponentially many bits, and hence, cannot serve as certificates to prove membership in class NP for either class of graphs.

This is a partially negative result because it is contingent on the special encoding the authors use; perhaps with a better and more compressed encoding of such graphs, one might be able to generate certificates for NP membership, thus proving that these NP-hard problems are indeed NP-complete.

Overall, this is a well-written paper that solves two important problems, and makes an essential observation toward another important problem (NP-completeness). It is rigorous, but reads well--from the introduction, through the proofs, to the end.