A disk contact graph is a graph that can be represented by a set of interior-disjoint disks in the plane, where each disk represents a vertex and an edge between two disks exists if and only if the disks touch (or kiss). Many studies have been conducted to classify the types of graphs that can be represented as disk contact graphs as well as to design algorithms to find a set of disks that represent the graph (or to determine if this is even possible). A fundamental results in this area is Koebe's theorem, which states that every planar graph can be represented as a contact graph of disks [5].
展开▼
