Contact graph

From Wikipedia, the free encyclopedia

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
  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), "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; 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
  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
  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
  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
Stub icon

This combinatorics-related article is a stub. You can help Wikipedia by .

  • v
  • t
Retrieved from ""