Sphere-of-Influence Graphs
Requires a Wolfram Notebook System
Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.
Let 
be a set of vertices chosen from a grid. Given a vertex 
in 
, let 
be the closest neighbor to 
in 
and draw a circle with center 
and radius 
. Draw an edge between two vertices 
and 
if their circles intersect. In other words, connect 
and 
if 
. This gives the sphere-of-influence graph for the given set of vertices.
Contributed by: Edray Herber Goins and Talitha M. Washington (March 2011)
Open content licensed under CC BY-NC-SA
Snapshots
Details
References:
G. T. Toussaint, "A Graph-Theoretic Primal Sketch," Computational Morphology (G. T. Toussaint, ed.), Amsterdam: Elsevier, 1988 pp. 220–260.
M. J. Lipman, "Integer Realizations of Sphere-of-Influence Graphs," Congr. Numer., 91, 1991 pp. 63–70.
Thickness of Sphere-of-Influence Graphs (2007)
Permanent Citation
"Sphere-of-Influence Graphs"
http://demonstrations.wolfram.com/SphereOfInfluenceGraphs/
Wolfram Demonstrations Project
Published: March 7 2011
Alternating Planar Graphs
Karl Scherer
Relations and Graphs
Jaime Rangel-Mondragon
Constructing and Manipulating Graphs
Karl Scherer
Enumerating the Directed Graphs
Seth J. Chandler
Average Vertex Degree of Connected Graphs
John Cicilio
Beraha's Conjecture, Wheels, and Cyclic Graphs
Jacqueline Zizi
Tridimensional Trivalent Graph
Raymond Aschheim
Graph Puzzles
Karl Scherer
Coloring Cycle Decompositions in Complete Graphs on a Prime Number of Vertices
Michael Morrison
De Bruijn Graph Arcs
Michael Schreiber