Adjacency Graph

Suppose we have a collection of objects, some of which are thought to be adjacent to others. Examples may be apples in a crate, regions in an electorate, or office workers who interact in a given project.

Define a graph by taking a vertex per object and joining two vertices with an edge if the objects are adjacent. This is the Adjacency Graph.

An unexpected example turns up in juggling. Suppose you juggle at a steady rhythm with the hands alternating. At any given moment, your choice of throw height is limited by the pattern of balls already in the air. The landing times of those balls gives what is called a "landing schedule", and two landing schedules, A and B, are adjacent if some throw you can make now from landing schedule A then puts you at the next time to throw at landing schedule B. This gives a LabelledDirectedGraph that contains every possible JugglingSiteSwap.

A less unexpected example is the duality between the VoronoiDiagram and the DelaunayTriangulation. adj


EditText of this page (last edited October 18, 2010) or FindPage with title or text search