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 according to some specified notion.[1]

Planar graphs have various types of geometric representations, they are known to be representable as contacting disks, triangles or – in the bipartite case – vertical and horizontal segments.

There have been many papers about the representation of planar graphs as contact graphs. An early result is Koebe’s 1936 theorem[2] proving that all planar graphs can be represented by touching disks.

See also

References

  1. ↑ Chaplick, Steven; G. Kobourov, Stephen; Ueckerdt, Torsten (2013-06-19). "Equilateral L-Contact Graphs". arXiv:1303.1279Freely accessible. online PDF
  2. ↑ Koebe, Paul (1936), "Kontaktprobleme der Konformen Abbildung", Ber. Sächs. Akad. Wiss. Leipzig, Math.-Phys. Kl., 88: 141–164
This article is issued from Wikipedia - version of the 9/18/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.