Sphericity (graph theory)

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.

[1][2] The concept of sphericity was first introduced by Hiroshi Maehara in the early 1980s.

can be realized as an intersection graph of unit spheres in

[4] Sphericity can also be defined using the language of space graphs as follows.

For a finite set of points in some

-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.

is isomorphic to a space graph in

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

denotes the number of vertices of

A graph of the vertices of a pentagon, realized as an intersection graph of disks in the plane. This is an example of a graph with sphericity 2, also known as a unit disk graph .