Pairwise Compatibility Graphs: A Survey

A graph G = (V, E) is a pairwise compatibility graph (PCG) if there exists an edge-weighted tree T and two nonnegative real numbers d(min) and d(max) such that each leaf u of T is a node of V and there is an edge (u, v) is an element of E if and only if d(min) <= d(T) (u, v) <= d(max), where d(T) (u, v) is the sum of weights of the edges on the unique path from u to v in T. In this article, we survey the state of the art concerning this class of graphs and some of its subclasses.