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.