Penny graph

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.

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.

Constructing a penny graph from the locations of its n circles can be performed in time O(n log n), as an instance of the closest pair of points problem, or alternatively by constructing the Delaunay triangulation or nearest neighbor graph of the circle centers (both of which contain the penny graph as a subgraph) and then testing which edges correspond to circle tangencies.

...
Wikipedia