Penny graph

11 pennies, forming a penny graph with 11 vertices and 19 edges
The Hanoi graph as a penny graph (the contact graph of the black disks)

In geometric graph theory, a penny graph is a contact graph of unit circles. It is formed from a collection of unit circles that do not cross each other, by creating a vertex for each circle and an edge for every pair of tangent circles.[1] The circles can be represented physically by pennies, arranged without overlapping on a flat surface, with a vertex for each penny and an edge for each two pennies that touch.

Penny graphs have also been called unit coin graphs,[2] because they are the coin graphs formed from unit circles.[1] If each vertex is represented by a point at the center of its circle, then two vertices will be adjacent if and only if their distance is the minimum distance among all pairs of vertices. Therefore, penny graphs have also been called minimum-distance graphs,[3] smallest-distance graphs,[4] or closest-pairs graphs.[5] Similarly, in a mutual nearest neighbor graph that links pairs of points in the plane that are each other's nearest neighbors, each connected component is a penny graph, although edges in different components may have different lengths.[6]

Every penny graph is a unit disk graph and a matchstick graph. Like planar graphs more generally, they obey the four color theorem, but this theorem is easier to prove for penny graphs. Testing whether a graph is a penny graph, or finding its maximum independent set, is NP-hard; however, both upper and lower bounds are known for the size of the maximum independent set, higher than the bounds that are possible for arbitrary planar graphs.

  1. ^ Cite error: The named reference cffp was invoked but never defined (see the help page).
  2. ^ Cite error: The named reference csiz was invoked but never defined (see the help page).
  3. ^ Cite error: The named reference bmp was invoked but never defined (see the help page).
  4. ^ Cite error: The named reference rcv was invoked but never defined (see the help page).
  5. ^ Cite error: The named reference ew96 was invoked but never defined (see the help page).