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 crossing) according to some specified notion.^[1] 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^[2] states that every planar graph can be represented as a contact graph of circles. The contact graphs of unit circles are called penny graphs.^[3] Representations as contact graphs of triangles,^[4] rectangles,^[5] squares,^[6] line segments,^[7] or circular arcs^[8] have also been studied.

References

1. Chaplick, Steven; Kobourov, Stephen G.; Ueckerdt, Torsten (2013), "Equilateral L-contact graphs", in Brandstädt, Andreas; Jansen, Klaus; Reischuk, Rüdiger (eds.), Graph-Theoretic Concepts in Computer Science - 39th International Workshop, WG 2013, Lübeck, Germany, June 19-21, 2013, Revised Papers, Lecture Notes in Computer Science, vol. 8165, Springer, pp. 139–151, arXiv:1303.1279, doi:10.1007/978-3-642-45043-3_13, S2CID 13541242
2. Koebe, Paul (1936), "Kontaktprobleme der Konformen Abbildung", Ber. Sächs. Akad. Wiss. Leipzig, Math.-Phys. Kl., 88: 141–164
3. Pisanski, Tomaž; Randić, Milan (2000), (PDF), in Gorini, Catherine A. (ed.), Geometry at Work, MAA Notes, vol. 53, Cambridge University Press, pp. 174–194, MR 1782654, archived from the original (PDF) on 2022-01-19, retrieved 2017-02-19; see especially p. 176
4. de Fraysseix, Hubert; Ossona de Mendez, Patrice; Rosenstiehl, Pierre (1994), "On triangle contact graphs", Combinatorics, Probability and Computing, 3 (2): 233–246, doi:10.1017/S0963548300001139, MR 1288442, S2CID 46160405
5. Buchsbaum, Adam L.; Gansner, Emden R.; Procopiuc, Cecilia M.; Venkatasubramanian, Suresh (2008), "Rectangular layouts and contact graphs", ACM Transactions on Algorithms, 4 (1): Art. 8, 28, arXiv:cs/0611107, doi:10.1145/1328911.1328919, MR 2398588, S2CID 1038771
6. Klawitter, Jonathan; Nöllenburg, Martin; Ueckerdt, Torsten (2015), "Combinatorial properties of triangle-free rectangle arrangements and the squarability problem", Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, Los Angeles, CA, USA, September 24-26, 2015, Revised Selected Papers, Lecture Notes in Computer Science, vol. 9411, Springer, pp. 231–244, arXiv:1509.00835, doi:10.1007/978-3-319-27261-0_20, S2CID 18477964
7. Hliněný, Petr (2001), "Contact graphs of line segments are NP-complete" (PDF), Discrete Mathematics, 235 (1–3): 95–106, doi:10.1016/S0012-365X(00)00263-6, MR 1829839
8. Alam, Md. Jawaherul; Eppstein, David; Kaufmann, Michael; Kobourov, Stephen G.; Pupyrev, Sergey; Schulz, André; Ueckerdt, Torsten (2015), "Contact graphs of circular arcs", Algorithms and Data Structures: 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015, Proceedings, Lecture Notes in Computer Science, vol. 9214, Springer, pp. 1–13, arXiv:1501.00318, doi:10.1007/978-3-319-21840-3_1, S2CID 6454732