Sphericity (graph theory)

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 an 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 the early 1980s.

This article is issued from Wikipedia. The text is available under Creative Commons Attribution-Share Alike 4.0 unless otherwise noted. Additional terms may apply for the media files.