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. 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 states that every planar graph can be represented as a contact graph of circles, known as a coin graph. Oded Schramm's monster packing theorem generalizes this: every planar graph is a contact graph of homothetic copies of any given smooth convex set. The contact graphs of unit circles are called penny graphs. Representations as contact graphs of triangles, rectangles, squares, line segments, or circular arcs 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, ISBN 978-3-642-45042-6, S2CID 13541242
  2. ↑ Koebe, Paul (1936), "Kontaktprobleme der Konformen Abbildung", Ber. Sächs. Akad. Wiss. Leipzig, Math.-Phys. Kl., 88: 141–164
  3. ↑ Schramm, Oded (1990), Packing Two-Dimensional Bodies With Prescribed Combinatorics And Applications To The Construction of Conformal and Quasi-Conformal Mappings (Ph.D. thesis), Princeton University, ProQuest 303827410; modified and reprinted as "Combinatorically Prescribed Packings and Applications to Conformal and Quasiconformal Maps", arXiv:0709.0710, 2007
  4. ↑ Pisanski, Tomaž; Randić, Milan (2000), "Bridges between geometry and graph theory" ( (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 on 2022-01-19, retrieved 2017-02-19; see especially p. 176
  5. ↑ 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
  6. ↑ 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
  7. ↑ 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, ISBN 978-3-319-27260-3, S2CID 18477964
  8. ↑ 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
  9. ↑ 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, ISBN 978-3-319-21839-7, S2CID 6454732