In geometric graph theory, a penny graph is a contact graph of unit circles. That is, it is an undirected graph whose vertices can be represented by unit circles, with no two of these circles crossing each other, and with two adjacent vertices if and only if they are represented by tangent circles. More simply, they are the graphs formed by arranging pennies in a non-overlapping way on a flat surface, making a vertex for each penny, and making an edge for each two pennies that touch. Penny graphs have also been called unit coin graphs, because they are the coin graphs formed from unit circles. If each vertex is represented by a point 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 points. Therefore, penny graphs have also been called minimum-distance graphs, smallest-distance graphs, or closest-pairs graphs. 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. 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.
Computational complexity
Constructing a penny graph from the locations of its circles can be performed as an instance of the closest pair of points problem, taking worst-case time or expected time. An alternative method with the same worst-case time is to construct the Delaunay triangulation or nearest neighbor graph of the circle centers and then test which edges correspond to circle tangencies. However, testing whether a given graph is a penny graph is NP-hard, even when the given graph is a tree. Similarly, testing whether a graph is a three-dimensional mutual nearest neighbor graph is also NP-hard.
Related graph families
Penny graphs are a special case of the coin graphs. Because the coin graphs are the same as the planar graphs, all penny graphs are planar. The penny graphs are also unit disk graphs, unit distance graphs, and matchstick graphs. The Hanoi graphs are penny graphs.
Number of edges
Every vertex in a penny graph has at most six neighboring vertices; here the number six is the kissing number for circles in the plane. However, the pennies whose centers are less than three units from the convex hull of the pennies have fewer neighbors. Based on a more precise version of this argument, one can show that every penny graph with vertices has at most edges. Some penny graphs, formed by arranging the pennies in a triangular grid, have exactly this number of edges. By arranging the pennies in a square grid, or in the form of certain squaregraphs, one can form triangle-free penny graphs whose number of edges is at least Swanepoel suggested that this bound is tight. Proving this, or finding a better bound, remains open. It is known that the number of edges can be at most but the coefficient of the square root does not match Swanepoel's conjecture.
Coloring
Every penny graph contains a vertex with at most three neighbors. For instance, such a vertex can be found at one of the corners of the convex hull of the circle centers, or as one of the two farthest-apart circle centers. Therefore, penny graphs have degeneracy at most three. Based on this, one can prove that their graph colorings require at most four colors, much more easily than the proof of the more general four-color theorem. However, despite their restricted structure, there exist penny graphs that do still require four colors. Analogously, the degeneracy of every triangle-free penny graph is at most two. Every such graph contains a vertex with at most two neighbors, even though it is not always possible to find this vertex on the convex hull. Based on this one can prove that they require at most three colors, more easily than the proof of the more general Grötzsch's theorem that triangle-free planar graphs are 3-colorable.
Independent sets
A maximum independent set in a penny graph is a subset of the pennies, no two of which touch each other. Finding maximum independent sets is NP-hard for arbitrary graphs, and remains NP-hard on penny graphs. It is an instance of the maximum disjoint set problem, in which one must find large subsets of non-overlapping regions of the plane. However, as with planar graphs more generally, Baker's technique provides a polynomial-time approximation scheme for this problem. In 1983, Paul Erdős asked for the largest number such that every -vertex penny graph has an independent set of at least vertices. That is, if we place pennies on a flat surface, there should be a subset of of the pennies that don't touch each other. By the four-color theorem,, and the improved bound was proven by Swanepoel. In the other direction, Pach and Tóth proved that. As of 2013, these remained the best bounds known for this problem.
