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.
ell
was invoked but never defined (see the help page).Koebe
was invoked but never defined (see the help page).bridges
was invoked but never defined (see the help page).triangle
was invoked but never defined (see the help page).rectangular
was invoked but never defined (see the help page).squarability
was invoked but never defined (see the help page).segments
was invoked but never defined (see the help page).arcs
was invoked but never defined (see the help page).