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
- ↑ Chaplick, Steven; Kobourov, Stephen G.; Ueckerdt, Torsten (2013), "Equilateral L-contact graphs", in Brandstädt, Andreas; Jansen, Klaus; Reischuk, Rüdiger, 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, 8165, Springer, pp. 139–151, doi:10.1007/978-3-642-45043-3_13
- ↑ "Kontaktprobleme der Konformen Abbildung", Ber. Sächs. Akad. Wiss. Leipzig, Math.-Phys. Kl. 88: 141–164, 1936
- ↑ Pisanski, Tomaž; Randić, Milan (2000), "Bridges between geometry and graph theory", in Gorini, Catherine A., Geometry at Work, MAA Notes, 53, Cambridge University Press, pp. 174–194, http://preprinti.imfm.si/PDF/00595.pdf, retrieved 2017-02-19; see especially p. 176
- ↑ de Fraysseix, Hubert (1994), "On triangle contact graphs", Combinatorics, Probability and Computing 3 (2): 233–246, doi:10.1017/S0963548300001139
- ↑ 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, doi:10.1145/1328911.1328919
- ↑ 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, 9411, Springer, pp. 231–244, doi:10.1007/978-3-319-27261-0_20
- ↑ Hliněný, Petr (2001), "Contact graphs of line segments are NP-complete", Discrete Mathematics 235 (1–3): 95–106, doi:10.1016/S0012-365X(00)00263-6, http://www.fi.muni.cz/~hlineny/papers/cont-seg.pdf
- ↑ Alam, Md. Jawaherul (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, 9214, Springer, pp. 1–13, doi:10.1007/978-3-319-21840-3_1
 |  |
