In geometric graph theory, a penny graph is a

contact graph In the mathematical area of graph theory, a contact graph or tangency graph is a graph whose vertices are represented by geometric objects (e.g. curves, line segments, or polygons), and whose edges correspond to two objects touching (but not cross ...

unit circle In mathematics, a unit circle is a circle of unit radius—that is, a radius of 1. Frequently, especially in trigonometry, the unit circle is the circle of radius 1 centered at the origin (0, 0) in the Cartesian coordinate system in the Eucl ...

s. 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 In geometry, tangent circles (also known as kissing circles) are circles in a common plane that intersect in a single point. There are two types of tangency: internal and external. Many problems and constructions in geometry are related to tangen ...

. 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, because they are the

coin graph The circle packing theorem (also known as the Koebe–Andreev–Thurston theorem) describes the possible tangency relations between circles in the plane whose interiors are disjoint. A circle packing is a connected collection of circles (in gen ...

s formed from unit circles. 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 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 In geometric graph theory, a unit disk graph is the intersection graph of a family of unit disks in the Euclidean plane. That is, it is a graph with one vertex for each disk in the family, and with an edge between two vertices whenever the corr ...

and a

matchstick graph In geometric graph theory, a branch of mathematics, a matchstick graph is a graph that can be drawn in the plane in such a way that its edges are line segments with length one that do not cross each other. That is, it is a graph that has an em ...

. Like

planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...

s more generally, they obey the

four color theorem In mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. ''Adjacent'' means that two regions sh ...

, 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 In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...

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

Properties

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 on the boundary of the

convex hull In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space ...

have fewer neighbors. Counting more precisely this reduction in neighbors for boundary pennies leads to a precise bound on the number of edges in any penny graph: a penny graph with vertices has at most

\left\lfloor 3n - \sqrt\right\rfloor

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 In geometry, the square tiling, square tessellation or square grid is a regular tiling of the Euclidean plane. It has Schläfli symbol of meaning it has 4 squares around every vertex. Conway called it a quadrille. The internal angle of the s ...

, or in the form of certain squaregraphs, one can form

triangle-free In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with g ...

penny graphs whose number of edges is at least

\left\lfloor 2n-2\sqrt\right\rfloor,

and in any triangle-free penny graph the number of edges is at most

2n-1.65\sqrt.

Swanepoel conjectured that the

\left\lfloor 2n-2\sqrt\right\rfloor

bound is tight. Proving this, or finding a better bound, remains open.

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

of the circle centers. Therefore, penny graphs have

degeneracy Degeneracy, degenerate, or degeneration may refer to: Arts and entertainment * ''Degenerate'' (album), a 2010 album by the British band Trigger the Bloodshed * Degenerate art, a term adopted in the 1920s by the Nazi Party in Germany to descri ...

at most three. Based on this, one can prove that their

graph coloring In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...

s require at most four colors, much more easily than the proof of the more general

four-color theorem In mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. ''Adjacent'' means that two regions sha ...

. 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

for arbitrary graphs, and remains

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 In theoretical computer science, Baker's technique is a method for designing polynomial-time approximation schemes (PTASs) for problems on planar graphs. It is named after Brenda Baker, who announced it in a 1983 conference and published it in the ' ...

provides a polynomial-time approximation scheme for this problem. In 1983,

Paul Erdős Paul Erdős ( hu, Erdős Pál ; 26 March 1913 – 20 September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in ...

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 do not 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.

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 The closest pair of points problem or closest pair problem is a problem of computational geometry: given n points in metric space, find a pair of points with the smallest distance between them. The closest pair problem for points in the Euclidean ...

, taking worst-case time or (with randomized time and with the use of the floor function) expected time . An alternative method with the same worst-case time is to construct the Delaunay triangulation or

nearest neighbor graph The nearest neighbor graph (NNG) is a directed graph defined for a set of points in a metric space, such as the Euclidean distance in the plane. The NNG has a vertex for each point, and a directed edge from ''p'' to ''q'' whenever ''q'' is a neare ...

of the circle centers (both of which contain the penny graph as a subgraph) and then test which edges correspond to circle tangencies. However, if a graph is given without geometric positions for its vertices, then testing whether it can be represented as a penny graph is

. It remains NP-hard even when the given graph is a

tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...

. Similarly, testing whether a graph can be represented as a three-dimensional mutual nearest neighbor graph is also NP-hard. 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.

Related graph families

Penny graphs are a special case of the coin graphs (graphs that can be represented by tangencies of non-crossing circles of arbitrary radii). Because the coin graphs are the same as the

s, all penny graphs are planar. The penny graphs are also

s (the intersection graphs of unit circles),

unit distance graph In mathematics, particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points whenever the distance between them is exactly one. To distinguish these graph ...

s (graphs that can be drawn with all edges having equal lengths, allowing crossings), and

s (graphs that can be drawn in the plane with equal-length straight edges and no edge crossings).

References

{{reflist, refs= {{citation , last = Baker, first = B. , authorlink = Brenda Baker , journal = Journal of the ACM , title = Approximation algorithms for NP-complete problems on planar graphs , volume = 41 , issue = 1 , year = 1994 , pages = 153–180 , doi = 10.1145/174644.174650, s2cid = 9706753 . {{citation , last1 = Bowen , first1 = Clinton , last2 = Durocher , first2 = Stephane , last3 = Löffler , first3 = Maarten , last4 = Rounds , first4 = Anika , last5 = Schulz , first5 = André , last6 = Tóth , first6 = Csaba D. , editor1-last = Giacomo , editor1-first = Emilio Di , editor2-last = Lubiw , editor2-first = Anna , editor2-link = Anna Lubiw , contribution = Realization of simply connected polygonal linkages and recognition of unit disk contact trees , doi = 10.1007/978-3-319-27261-0_37 , doi-access = free , pages = 447–459 , publisher = Springer , series =

Lecture Notes in Computer Science ''Lecture Notes in Computer Science'' is a series of computer science books published by Springer Science+Business Media since 1973. Overview The series contains proceedings, post-proceedings, monographs, and Festschrifts. In addition, tutorials, ...

, title = Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, Los Angeles, CA, USA, September 24–26, 2015, Revised Selected Papers , title-link = International Symposium on Graph Drawing , volume = 9411 , year = 2015 {{citation , last1 = Bhore , first1 = Sujoy , last2 = Jain , first2 = Rahul , editor1-last = Ahn , editor1-first = Hee-Kap , editor2-last = Sadakane , editor2-first = Kunihiko , contribution = Space-efficient algorithms for reachability in directed geometric graphs , contribution-url = https://drops.dagstuhl.de/opus/volltexte/2021/15496 , doi = 10.4230/LIPIcs.ISAAC.2021.63 , isbn = 978-3-95977-214-3 , location = Dagstuhl, Germany , pages = 63:1–63:17 , publisher = Schloss Dagstuhl – Leibniz-Zentrum für Informatik , series = Leibniz International Proceedings in Informatics (LIPIcs) , title = 32nd International Symposium on Algorithms and Computation (ISAAC 2021) , volume = 212 , year = 2021 {{citation , last1 = Brass , first1 = Peter , last2 = Moser , first2 = William , last3 = Pach , first3 = János , author3-link = János Pach , isbn = 978-0387-23815-9 , mr = 2163782 , page = 228 , publisher = Springer , location = New York , title = Research Problems in Discrete Geometry , url = https://books.google.com/books?id=WehCspo0Qa0C&pg=PA228 , year = 2005 {{citation , last1 = Cerioli , first1 = Marcia R. , last2 = Faria , first2 = Luerbio , last3 = Ferreira , first3 = Talita O. , last4 = Protti , first4 = Fábio , doi = 10.1051/ita/2011106 , issue = 3 , journal = RAIRO Theoretical Informatics and Applications , mr = 2836493 , pages = 331–346 , title = A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation , url = http://www.numdam.org/item/ITA_2011__45_3_331_0/ , volume = 45 , year = 2011 {{citation , last = Csizmadia , first = G. , doi = 10.1007/PL00009381 , doi-access = free , issue = 2 , journal = Discrete and Computational Geometry , mr = 1637884 , pages = 179–187 , title = On the independence number of minimum distance graphs , volume = 20 , year = 1998 {{citation , last1 = Dumitrescu , first1 = Adrian , last2 = Jiang , first2 = Minghui , arxiv = cs/9908007 , date = June 2013 , doi = 10.1145/2491533.2491550 , issue = 2 , journal = SIGACT News , location = New York, NY, USA , pages = 80–87 , publisher = ACM , title = Computational Geometry Column 56 , url = http://www.cs.uwm.edu/faculty/ad/column56.pdf , volume = 44, s2cid = 52807205 {{citation, title=Graphs defined by matchsticks, pennies and hinges, work=Discrete notes, date=May 29, 2019, first=Laurent, last=Feuilloley, url=https://discrete-notes.github.io/april-may-2019-notes {{citation , last = Eppstein , first = David , authorlink = David Eppstein , arxiv = 1708.05152 , doi = 10.7155/jgaa.00463 , doi-access = free , issue = 3 , journal =

Journal of Graph Algorithms and Applications The ''Journal of Graph Algorithms and Applications'' is an open access peer-reviewed scientific journal covering the subject of graph algorithms and graph drawing. The journal was established in 1997 and the editor-in-chief is Giuseppe Liotta (Univ ...

, mr = 3866392 , pages = 483–499 , title = Edge bounds and degeneracy of triangle-free penny graphs and squaregraphs , volume = 22 , year = 2018 {{citation , last1 = Eades , first1 = Peter , author1-link = Peter Eades , last2 = Whitesides , first2 = Sue , author2-link = Sue Whitesides , doi = 10.1016/S0304-3975(97)84223-5 , doi-access = free , issue = 1 , journal =

Theoretical Computer Science Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumsc ...

, mr = 1424926 , pages = 23–37 , title = The logic engine and the realization problem for nearest neighbor graphs , volume = 169 , year = 1996 {{citation, first=H., last=Harborth, authorlink=Heiko Harborth, title=Lösung zu Problem 664A, journal=

Elemente der Mathematik ''Elemente der Mathematik'' is a peer-reviewed scientific journal covering mathematics. It is published by the European Mathematical Society, European Mathematical Society Publishing House on behalf of the Swiss Mathematical Society. It was establ ...

, volume=29, year=1974, pages=14–15. As cited by {{harvtxt, Swanepoel, 2009 and {{harvtxt, Pach, Agarwal, 1995. {{citation , last1 = Horvat , first1 = Boris , last2 = Pisanski , first2 = Tomaž , author2-link = Tomaž Pisanski , doi = 10.1016/j.disc.2009.11.035 , issue = 12 , journal =

Discrete Mathematics Discrete mathematics is the study of mathematical structures that can be considered "discrete" (in a way analogous to discrete variables, having a bijection with the set of natural numbers) rather than "continuous" (analogously to continuous f ...

, mr = 2610282 , pages = 1783–1792 , title = Products of unit distance graphs , volume = 310 , year = 2010, doi-access = free {{citation , last1 = Khuller , first1 = Samir , last2 = Matias , first2 = Yossi , doi = 10.1006/inco.1995.1049 , doi-access = free , issue = 1 , journal = Information and Computation , mr = 1329236 , pages = 34–37 , title = A simple randomized sieve algorithm for the closest-pair problem , volume = 118 , year = 1995 {{citation , last = Kupitz , first = Y. S. , contribution = On the maximal number of appearances of the minimal distance among {{mvar, n points in the plane , mr = 1383628 , pages = 217–244 , publisher = North-Holland , series = Colloq. Math. Soc. János Bolyai , title = Intuitive Geometry (Szeged, 1991) , volume = 63 , year = 1994 {{citation , last1 = Kitching , first1 = Matthew , last2 = Whitesides , first2 = Sue , author2-link = Sue Whitesides , editor-last = Pach , editor-first = János , editor-link = János Pach , contribution = The Three Dimensional Logic Engine , doi = 10.1007/978-3-540-31843-9_33 , doi-access = free , pages = 329–339 , publisher = Springer , series = Lecture Notes in Computer Science , title = Graph Drawing, 12th International Symposium, GD 2004, New York, NY, USA, September 29 - October 2, 2004, Revised Selected Papers , volume = 3383 , year = 2004 {{citation , last1 = Pisanski , first1 = Tomaž , author1-link = Tomaž Pisanski , last2 = Randić , first2 = Milan , editor-last = Gorini , editor-first = Catherine A. , contribution = Bridges between geometry and graph theory , contribution-url = http://preprinti.imfm.si/PDF/00595.pdf , mr = 1782654 , pages = 174–194 , publisher = Cambridge University Press , series = MAA Notes , title = Geometry at Work , volume = 53 , year = 2000; see especiall
p. 176
/ref> {{citation, title=Pearls in Graph Theory: A Comprehensive Introduction, title-link= Pearls in Graph Theory, series=Dover Books on Mathematics, first1=Nora, last1=Hartsfield, first2=Gerhard, last2=Ringel, author2-link=Gerhard Ringel, publisher=Courier Corporation, year=2013, isbn=9780486315522, contribution=Problem 8.4.8, pages=177–178, contribution-url=https://books.google.com/books?id=VMjDAgAAQBAJ&pg=PA177. {{citation , last1 = Pach , first1 = János , author1-link = János Pach , last2 = Agarwal , first2 = Pankaj K. , author2-link = Pankaj K. Agarwal , doi = 10.1002/9781118033203 , isbn = 0-471-58890-3 , location = New York , mr = 1354145 , publisher = John Wiley & Sons, Inc. , series = Wiley-Interscience Series in Discrete Mathematics and Optimization , title = Combinatorial Geometry , year = 1995; see Theorem 13.12, p. 211. {{citation , last1 = Pach , first1 = János , author1-link = János Pach , last2 = Tóth , first2 = Géza , issue = 1 , journal = Geombinatorics , mr = 1392795 , pages = 30–33 , title = On the independence number of coin graphs , url = https://infoscience.epfl.ch/record/129193/files/coincikk.ps , volume = 6 , year = 1996 {{citation , last = Veltkamp , first = Remco C. , contribution = 2.2.1 Closest pairs , doi = 10.1007/3-540-58808-6 , doi-access = free , isbn = 3-540-58808-6 , location = Berlin , page = 12 , publisher = Springer-Verlag , series = Lecture Notes in Computer Science , title = Closed Object Boundaries from Scattered Points , volume = 885 , year = 1994 {{citation , last = Swanepoel , first = Konrad J. , issue = 1 , journal = Geombinatorics , mr = 2584434 , pages = 28–30 , title = Triangle-free minimum distance graphs in the plane , url = http://personal.lse.ac.uk/SWANEPOE/swanepoel-min-dist.pdf , volume = 19 , year = 2009 {{citation , last = Swanepoel , first = Konrad J. , arxiv = math/0403023 , doi = 10.1007/s00454-002-2897-y , doi-access=free , issue = 4 , journal = Discrete and Computational Geometry , mr = 1949907 , pages = 649–670 , title = Independence numbers of planar contact graphs , volume = 28 , year = 2002; Swanepoel's result strengthens an earlier {{math, ''c'' ≥ 9/35 ≈ 0.257 bound of {{harvtxt, Csizmadia, 1998. Geometric graphs Planar graphs Circle packing