Penny Graph on:
[Wikipedia]
[Google]
[Amazon]
In
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 
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
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 =
In geometric graph theory
Geometric graph theory in the broader sense is a large and amorphous subfield of graph theory, concerned with graphs defined by geometric means. In a stricter sense, geometric graph theory studies combinatorial and geometric properties of geomet ...
, 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 ...
of 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 Eucli ...
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
A penny is a coin (: pennies) or a unit of currency (: pence) in various countries. Borrowed from the Carolingian denarius (hence its former abbreviation d.), it is usually the smallest denomination within a currency system. At present, it is t ...
, 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 graphs 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
In logic and related fields such as mathematics and philosophy, "if and only if" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either bo ...
their distance is the minimum distance among all pairs of vertices. 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 corres ...
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 ...
.
Like planar graph
In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...
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 shar ...
, but this theorem is easier to prove for penny graphs.
Testing whether a graph is a penny graph, or finding its maximum independent set
In mathematical analysis, the maximum and minimum of a function are, respectively, the greatest and least value taken by the function. Known generically as extremum, they may be defined either within a given range (the ''local'' or ''relative ...
, is NP-hard
In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...
; however, both upper and lower bounds
In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is every element of .
Dually, a lower bound or minorant of is defined to be an element of that is less th ...
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 thekissing number
In geometry, the kissing number of a mathematical space is defined as the greatest number of non-overlapping unit spheres that can be arranged in that space such that they each touch a common unit sphere. For a given sphere packing (arrangement o ...
for circles in the plane.
However, the pennies on the boundary of the convex hull
In geometry, the convex hull, 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
edges. Some penny graphs, formed by arranging the pennies in a triangular grid
In geometry, the triangular tiling or triangular tessellation is one of the three Euclidean tilings by convex regular polygons#Regular tilings, regular tilings of the Euclidean plane, and is the only such tiling where the constituent shapes are n ...
, 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 consisting of four squares around every vertex. John Horton Conway called it a quadrille.
Structure and properties
The square tiling ...
, or in the form of certain squaregraph
In graph theory, a branch of mathematics, a squaregraph is a type of undirected graph that can be drawn in the plane in such a way that every bounded face is a quadrilateral and every vertex with three or fewer neighbors is incident to an unboun ...
s, one can form triangle-free
In the mathematics, mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle graph, triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique (graph t ...
penny graphs whose number of edges is at least
and in any triangle-free penny graph the number of edges is at most
Swanepoel conjectured that the 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 convex hull
In geometry, the convex hull, 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, ...
of the circle centers. Therefore, penny graphs have degeneracy at most three. Based on this, one can prove that their graph coloring
In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a Graph (discrete mathematics), graph. The assignment is subject to certain constraints, such as that no two adjacent elements have th ...
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 shar ...
. 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
In the mathematics, mathematical field of graph theory, Grötzsch's theorem is the statement that every triangle-free graph, triangle-free planar graph can be graph coloring, colored with only three colors. According to the four-color theorem, eve ...
that triangle-free planar graphs are 3-colorable.
Independent sets
Amaximum independent set
In mathematical analysis, the maximum and minimum of a function are, respectively, the greatest and least value taken by the function. Known generically as extremum, they may be defined either within a given range (the ''local'' or ''relative ...
in a penny graph is a subset of the pennies, no two of which touch each other. Finding maximum independent sets is NP-hard
In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...
for arbitrary graphs, and remains NP-hard
In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...
on penny graphs. It is an instance of the maximum disjoint set
In computational geometry, a maximum disjoint set (MDS) is a largest set of non-overlapping geometric shapes selected from a given set of candidate shapes.
Every set of non-overlapping shapes is an independent set (graph theory), independent set i ...
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
In computer science (particularly algorithmics), a polynomial-time approximation scheme (PTAS) is a type of approximation algorithm for optimization problems (most often, NP-hard optimization problems).
A PTAS is an algorithm which takes an inst ...
for this problem.
In 1983, Paul Erdős
Paul Erdős ( ; 26March 191320September 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 discrete mathematics, g ...
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, taking worst-case time or (with randomized time and with the use of thefloor function
In mathematics, the floor function is the function that takes as input a real number , and gives as output the greatest integer less than or equal to , denoted or . Similarly, the ceiling function maps to the least integer greater than or eq ...
) expected time . An alternative method with the same worst-case time is to construct the Delaunay triangulation
In computational geometry, a Delaunay triangulation or Delone triangulation of a set of points in the plane subdivides their convex hull into triangles whose circumcircles do not contain any of the points; that is, each circumcircle has its gen ...
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 n ...
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 NP-hard
In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...
. 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, e.g., including only woody plants with secondary growth, only ...
. 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
In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...
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 theplanar graph
In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...
s, all penny graphs are planar. The penny graphs are also 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 corres ...
s (the intersection graph
In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types o ...
s of unit circles), unit distance graph
In mathematics, particularly geometric graph theory, a unit distance graph is a Graph (discrete mathematics), graph formed from a collection of points in the Euclidean plane by connecting two points whenever the distance between them is exactly o ...
s (graphs that can be drawn with all edges having equal lengths, allowing crossings), and 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 ...
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
The ''Journal of the ACM'' (''JACM'') is a peer-reviewed scientific journal covering computer science in general, especially theoretical aspects. It is an official journal of the Association for Computing Machinery. Its current editor-in-chief is ...
, 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
{{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, isbn = 978-3-319-27260-3
{{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, doi-access = free
, s2cid = 244731943
{{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 & Computational Geometry
'' Discrete & Computational Geometry'' is a peer-reviewed mathematics journal published quarterly by Springer. Founded in 1986 by Jacob E. Goodman and Richard M. Pollack, the journal publishes articles on discrete geometry and computational ...
, 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
ACM SIGACT or SIGACT is the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory, whose purpose is support of research in theoretical computer science. It was founded in 1968 by Patrick C. Fischer.
Publi ...
, 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
{{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 a diamond open access peer-reviewed scientific journal covering the subject of graph algorithms and graph drawing. The journal was established in 1997 and the current co-editors-in-chief are ...
, 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 is a subfield of computer science and mathematics that focuses on the Abstraction, abstract and mathematical foundations of computation.
It is difficult to circumscribe the theoretical areas precisely. The Associati ...
, mr = 1424926
, pages = 23–37
, title = The logic engine and the realization problem for nearest neighbor graphs
, volume = 169
, year = 1996
{{citation
, last = Gardner , first = Martin , author-link = Martin Gardner
, date = March 1975
, department = Mathematical Games
, issue = 3
, journal = Scientific American
''Scientific American'', informally abbreviated ''SciAm'' or sometimes ''SA'', is an American popular science magazine. Many scientists, including Albert Einstein and Nikola Tesla, have contributed articles to it, with more than 150 Nobel Pri ...
, 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
''Elemente der Mathematik'' is a peer-reviewed scientific journal covering mathematics. It is published by the European Mathematical Society Publishing House on behalf of the Swiss Mathematical Society. It was established in 1946 by Louis Loc ...
, 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, isbn = 978-3-540-24528-5
{{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 especiallp. 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
Alexander Soifer is a Russian-born American mathematician and mathematics author.
Soifer obtained his Ph.D. in 1973 and has been a professor of mathematics at the University of Colorado since 1979. He was visiting fellow at Princeton University ...
, 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
Alexander Soifer is a Russian-born American mathematician and mathematics author.
Soifer obtained his Ph.D. in 1973 and has been a professor of mathematics at the University of Colorado since 1979. He was visiting fellow at Princeton University ...
, 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 & Computational Geometry
'' Discrete & Computational Geometry'' is a peer-reviewed mathematics journal published quarterly by Springer. Founded in 1986 by Jacob E. Goodman and Richard M. Pollack, the journal publishes articles on discrete geometry and computational ...
, 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