Английская Википедия:Contact graph

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Шаблон:Short description 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.Шаблон:R 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Шаблон:R states that every planar graph can be represented as a contact graph of circles. The contact graphs of unit circles are called penny graphs.Шаблон:R Representations as contact graphs of triangles,Шаблон:R rectangles,Шаблон:R squares,Шаблон:R line segments,Шаблон:R or circular arcsШаблон:R have also been studied.

References

Шаблон:Reflist


Шаблон:Graph-stub