contact graph
{{Short description|Graph representing tangency between geometric objects}}
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 crossing) according to some specified notion.{{r|ell}} It is similar to the notion of an intersection graph but differs from it in restricting the ways that the underlying objects are allowed to intersect each other.
The circle packing theorem{{r|Koebe}} states that every planar graph can be represented as a contact graph of circles, known as a coin graph. The contact graphs of unit circles are called penny graphs.{{r|bridges}} Representations as contact graphs of triangles,{{r|triangle}} rectangles,{{r|rectangular}} squares,{{r|squarability}} line segments,{{r|segments}} or circular arcs{{r|arcs}} have also been studied.
References
{{reflist|refs=
| last1 = Alam | first1 = Md. Jawaherul
| last2 = Eppstein | first2 = David | author2-link = David Eppstein
| last3 = Kaufmann | first3 = Michael
| last4 = Kobourov | first4 = Stephen G.
| last5 = Pupyrev | first5 = Sergey
| last6 = Schulz | first6 = André
| last7 = Ueckerdt | first7 = Torsten
| arxiv = 1501.00318
| contribution = Contact graphs of circular arcs
| doi = 10.1007/978-3-319-21840-3_1
| pages = 1–13
| publisher = Springer
| series = Lecture Notes in Computer Science
| title = Algorithms and Data Structures: 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015, Proceedings
| volume = 9214
| year = 2015| s2cid = 6454732
}}
| 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
| access-date = 2017-02-19
| archive-date = 2022-01-19
| archive-url = https://web.archive.org/web/20220119095601/http://preprinti.imfm.si/PDF/00595.pdf
| url-status = dead
}}; see especially [https://books.google.com/books?id=Eb6uSLa2k6IC&pg=PA176 p. 176]
| last1 = Chaplick | first1 = Steven
| last2 = Kobourov | first2 = Stephen G.
| last3 = Ueckerdt | first3 = Torsten
| editor1-last = Brandstädt | editor1-first = Andreas
| editor2-last = Jansen | editor2-first = Klaus
| editor3-last = Reischuk | editor3-first = Rüdiger
| arxiv = 1303.1279
| contribution = Equilateral L-contact graphs
| doi = 10.1007/978-3-642-45043-3_13
| pages = 139–151
| publisher = Springer
| series = Lecture Notes in Computer Science
| title = Graph-Theoretic Concepts in Computer Science - 39th International Workshop, WG 2013, Lübeck, Germany, June 19-21, 2013, Revised Papers
| volume = 8165
| year = 2013| s2cid = 13541242
}}
| last1 = de Fraysseix | first1 = Hubert
| last2 = Ossona de Mendez | first2 = Patrice | author2-link = Patrice Ossona de Mendez
| last3 = Rosenstiehl | first3 = Pierre | author3-link = Pierre Rosenstiehl
| doi = 10.1017/S0963548300001139
| issue = 2
| journal = Combinatorics, Probability and Computing
| mr = 1288442
| pages = 233–246
| title = On triangle contact graphs
| volume = 3
| year = 1994| s2cid = 46160405
}}
| last = Koebe | first = Paul | author-link = Paul Koebe
| journal = Ber. Sächs. Akad. Wiss. Leipzig, Math.-Phys. Kl.
| pages = 141–164
| title = Kontaktprobleme der Konformen Abbildung
| volume = 88
| year = 1936}}
| last1 = Buchsbaum | first1 = Adam L.
| last2 = Gansner | first2 = Emden R.
| last3 = Procopiuc | first3 = Cecilia M.
| last4 = Venkatasubramanian | first4 = Suresh
| arxiv = cs/0611107
| doi = 10.1145/1328911.1328919
| issue = 1
| journal = ACM Transactions on Algorithms
| mr = 2398588
| page = Art. 8, 28
| title = Rectangular layouts and contact graphs
| volume = 4
| year = 2008| s2cid = 1038771
}}
| last = Hliněný | first = Petr
| doi = 10.1016/S0012-365X(00)00263-6 | doi-access = free
| issue = 1–3
| journal = Discrete Mathematics
| mr = 1829839
| pages = 95–106
| title = Contact graphs of line segments are NP-complete
| url = http://www.fi.muni.cz/~hlineny/papers/cont-seg.pdf
| volume = 235
| year = 2001}}
| last1 = Klawitter | first1 = Jonathan
| last2 = Nöllenburg | first2 = Martin
| last3 = Ueckerdt | first3 = Torsten
| arxiv = 1509.00835
| contribution = Combinatorial properties of triangle-free rectangle arrangements and the squarability problem
| doi = 10.1007/978-3-319-27261-0_20
| pages = 231–244
| 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
| volume = 9411
| year = 2015| s2cid = 18477964
}}
}}
Category:Geometric graph theory
{{graph-stub}}