Penny graph
{{Short description|Graph formed by touching unit circles}}
File:Sierpinski Pascal triangle.svg 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.{{r|links}} 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,{{r|cffp}} because they are the coin graphs formed from unit circles.{{r|links}} 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,{{r|csiz}} smallest-distance graphs,{{r|bmp}} or closest-pairs graphs.{{r|rcv}} 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.{{r|ew96}}
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.
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 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 {{mvar|n}} vertices has at most
edges. Some penny graphs, formed by arranging the pennies in a triangular grid, have exactly this number of edges.{{r|harborth|pj95|kupitz}}
{{unsolved|mathematics|What is the maximum number of edges in a triangle-free penny graph?}}
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
and in any triangle-free penny graph the number of edges is at most{{r|eppstein}}
Swanepoel conjectured that the bound is tight.{{r|swanepoel}} 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 convex hull of the 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.{{r|pearls}} However, despite their restricted structure, there exist penny graphs that do still require four colors.{{r|gardner}}
File:Triangle-free penny graph.jpg penny graph with the property that all the pennies on the convex hull touch at least three other pennies]]
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.{{r|eppstein}}
=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.{{r|cffp}} 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.{{r|baker}}
{{unsolved|mathematics|What is the largest such that every {{nowrap|-vertex}} penny graph has an independent set of size ?}}
In 1983, Paul Erdős asked for the largest number {{mvar|c}} such that every {{mvar|n}}-vertex penny graph has an independent set of at least {{mvar|cn}} vertices.{{r|pt96}} That is, if we place {{mvar|n}} pennies on a flat surface, there should be a subset of {{mvar|cn}} of the pennies that do not touch each other. By the four-color theorem, {{math|c ≥ 1/4}}, and the improved bound {{math|c ≥ 8/31 ≈ 0.258}} was proven by Swanepoel.{{r|swan2}} In the other direction, Pach and Tóth proved that {{math|1=c ≤ 5/16 = 0.3125}}.{{r|pt96}} As of 2013, these remained the best bounds known for this problem.{{r|bmp|dj13}}
Computational complexity
Constructing a penny graph from the locations of its {{mvar|n}} circles can be performed as an instance of the closest pair of points problem, taking worst-case time {{math|O(n log n)}}{{r|rcv}} or (with randomized time and with the use of the floor function) expected time {{math|O(n)}}.{{r|km95}} 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){{r|rcv}} 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 NP-hard.{{r|ew96}} It remains NP-hard even when the given graph is a tree.{{r|bdlrst}} Similarly, testing whether a graph can be represented as a three-dimensional mutual nearest neighbor graph is also NP-hard.{{r|kw04}}
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.{{r|bj21}}
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).{{r|links}} Because the coin graphs are the same as the planar graphs,{{sfnp|Hartsfield|Ringel|2013|loc=Theorem 8.4.2, p. 173}} all penny graphs are planar. The penny graphs are also unit disk graphs (the intersection graphs of unit circles),{{r|cffp}} unit distance graphs (graphs that can be drawn with all edges having equal lengths, allowing crossings),{{r|hp10}} and matchstick graphs (graphs that can be drawn in the plane with equal-length straight edges and no edge crossings).{{r|dn}}
References
{{reflist|refs=
| 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 | doi-access = free
}}
| 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
| 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| isbn = 978-3-319-27260-3
}}
| 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| doi-access = free
| s2cid = 244731943
}}
| 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}}
| 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}}
| last = Csizmadia | first = G.
| doi = 10.1007/PL00009381 | doi-access = free
| issue = 2
| journal = Discrete & Computational Geometry
| mr = 1637884
| pages = 179–187
| title = On the independence number of minimum distance graphs
| volume = 20
| year = 1998}}
| 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, US
| pages = 80–87
| publisher = ACM
| title = Computational Geometry Column 56
| url = http://www.cs.uwm.edu/faculty/ad/column56.pdf
| volume = 44| s2cid = 52807205
}}
| 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
| mr = 3866392
| pages = 483–499
| title = Edge bounds and degeneracy of triangle-free penny graphs and squaregraphs
| volume = 22
| year = 2018}}
| 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
| mr = 1424926
| pages = 23–37
| title = The logic engine and the realization problem for nearest neighbor graphs
| volume = 169
| year = 1996}}
| last = Gardner | first = Martin | author-link = Martin Gardner
| date = March 1975
| department = Mathematical Games
| issue = 3
| journal = Scientific American
| jstor = 24949757
| pages = 112–117
| title = From rubber ropes to rolling cubes, a miscellany of refreshing problems
| volume = 232| doi = 10.1038/scientificamerican0375-112 }}; see problem 7, "the colored poker chips", p. 114.
{{citation|first=H.|last=Harborth|authorlink=Heiko Harborth|title=Lösung zu Problem 664A|journal=Elemente der Mathematik|volume=29|year=1974|pages=14–15}}. As cited by {{harvtxt|Swanepoel|2009}} and {{harvtxt|Pach|Agarwal|1995}}.
| 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
| mr = 2610282
| pages = 1783–1792
| title = Products of unit distance graphs
| volume = 310
| year = 2010| doi-access = free
}}
| 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}}
| 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}}
| 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| isbn = 978-3-540-24528-5
}}
| 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 especially [https://books.google.com/books?id=Eb6uSLa2k6IC&pg=PA176 p. 176]
| 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.
| 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}}
| 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}}
| 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}}
| last = Swanepoel | first = Konrad J.
| arxiv = math/0403023
| doi = 10.1007/s00454-002-2897-y | doi-access=free
| issue = 4
| journal = Discrete & 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}}.
}}