Sphericity (graph theory)

A graph with sphericity 2: A space graph of the vertices of a pentagon, realized as the intersection graph of the unit 2-disks in the plane, centered on these points. This is also known as a unit disk graph.

In the mathematical field of 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 the intersection graph of congruent spheres. The sphericity of a graph is one of several notions of graph dimension based on intersection graphs; others include boxicity and cubicity. The concept of sphericity was first introduced by Hiroshi Maehara in 1980 (and also used by Timothy F. Havel in 1982).