Pairwise compatibility graph
In graph theory, a graph  is a pairwise compatibility graph (PCG) if there exists a tree  and two non-negative real numbers  such that each node  of  has a one-to-one mapping with a leaf node  of  such that two nodes  and  are adjacent in  if and only if the distance between  and  are in the interval . The subclasses of PCG include graphs of at most seven vertices, cycles, forests, complete graphs, interval graphs and ladder graphs. However, there is a graph with eight vertices that is known not to be a PCG. Relationship to phylogenetics 
Pairwise compatibility graphs were first introduced by Paul Kearney, J. Ian Munro and Derek Phillips in the context of phylogeny reconstruction. When sampling from a phylogenetic tree, the task of finding nodes whose path distance lies between given lengths  is equivalent to finding a clique in the associated PCG. Complexity 
The computational complexity of recognizing a graph as a PCG is unknown as of 2020. However, the related problem of finding for a graph  and a selection of non-edge relations  a PCG containing  as a subgraph and with none of the edges in  is known to be NP-hard. The task of finding nodes in a tree whose paths distance lies between  and  is known to be solvable in polynomial time. Therefore, if the tree could be recovered from a PCG in polynomial time, then the clique problem on PCGs would be polynomial too. As of 2020, neither of these complexities is known. References 

Graph families
Computational phylogenetics