In graph theory, the sphericity of a graph is a graph invariant defined to be the smallest dimension of Euclidean space required to realize the graph as an intersection graph of unit spheres. The sphericity of a graph is a generalization of the boxicity and cubicity invariants defined by F.S. Roberts in the late 1960s. The concept of sphericity was first introduced by Hiroshi Maehara in the early 1980s.
Definition.
Let formula_1 be a graph. Then the "sphericity" of formula_1, denoted by formula_3, is the smallest integer formula_4 such that formula_1 can be realized as an intersection graph of unit spheres in formula_4-dimensional Euclidean space formula_7.
Sphericity can also be defined using the language of space graphs as follows. For a finite set of points in some formula_4-dimensional Euclidean space, a "space graph" is built by connecting pairs of points with a line segment when their Euclidean distance is less than some specified constant. Then the sphericity of a graph formula_1 is the minimum formula_4 such that formula_1 is isomorphic to a space graph in formula_7.
Graphs of sphericity 1 are known as interval graphs or indifference graphs. Graphs of sphericity 2 are known as unit disk graphs.
Bounds.
The sphericity of certain graph classes can be computed exactly. The following sphericities were given by Maehara on page 56 of his original paper on the topic.
The most general known upper bound on sphericity is as follows. Assuming the graph is not complete, then formula_13 where formula_14 is the clique number of formula_1 and formula_16 denotes the number of vertices of formula_17