Sphere-of-Influence Graphs on a Sphere

Abstract

Given a collection of points in the plane, a circle is drawn around each point with radius equal to the smallest distance from that point to any other in the collection. The sphere-of-influence graph is the intersection graph of the open balls given by these circles. Any graph isomorphic to such a graph is a SIG realizable in a plane. Similarly, one can define a SIG realizable on a sphere by selecting a collection of points on a sphere. We show that \(K_9\) is realizable as a SIG on a sphere and that the family of graphs realizable as SIGs on a sphere is at least as large as the family of SIGs in the plane.