Penny graph

[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.

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.

However, the pennies on the boundary of the convex hull have fewer neighbors.

For instance, such a vertex can be found at one of the corners of the convex hull of the circle centers.

[12] However, despite their restricted structure, there exist penny graphs that do still require four colors.

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.

[2] 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.

[14] In 1983, Paul Erdős asked for the largest number c such that every n-vertex penny graph has an independent set of at least cn vertices.

By the four-color theorem, c ≥ 1/4, and the improved bound c ≥ 8/31 ≈ 0.258 was proven by Swanepoel.

[4][17] Constructing a penny graph from the locations of its n circles can be performed as an instance of the closest pair of points problem, taking worst-case time O(n log n)[5] or (with randomized time and with the use of the floor function) expected time O(n).

[18] An alternative method with the same worst-case time is to construct the Delaunay triangulation or nearest neighbor graph of the circle centers (both of which contain the penny graph as a subgraph)[5] and then test which edges correspond to circle tangencies.

[20] It is possible to perform some computational tasks on directed penny graphs, such as testing whether one vertex can reach another, in polynomial time and substantially less than linear space, given an input representing its circles in a form allowing basic computational tasks such as testing adjacency and finding intersections of the circles with axis-parallel lines.