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, known as a coin graph. 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.