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. 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.

  1. ^ Cite error: The named reference ell was invoked but never defined (see the help page).
  2. ^ Cite error: The named reference Koebe was invoked but never defined (see the help page).
  3. ^ Cite error: The named reference bridges was invoked but never defined (see the help page).
  4. ^ Cite error: The named reference triangle was invoked but never defined (see the help page).
  5. ^ Cite error: The named reference rectangular was invoked but never defined (see the help page).
  6. ^ Cite error: The named reference squarability was invoked but never defined (see the help page).
  7. ^ Cite error: The named reference segments was invoked but never defined (see the help page).
  8. ^ Cite error: The named reference arcs was invoked but never defined (see the help page).