# Pairwise Compatibility Graphs: A Survey

Abstract : 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) \in E$ if and only if $d_{min} \leq d_T (u, v) \leq 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.
Keywords :
Document type :
Journal articles
Domain :

Cited literature [54 references]

https://hal.inria.fr/hal-01388533
Contributor : Marie-France Sagot <>
Submitted on : Monday, May 29, 2017 - 10:26:44 AM
Last modification on : Tuesday, July 20, 2021 - 5:20:05 PM
Long-term archiving on: : Wednesday, September 6, 2017 - 10:30:10 AM

### File

SurveyPCG.pdf
Files produced by the author(s)

### Citation

Tiziana Calamoneri, Blerina Sinaimeri. Pairwise Compatibility Graphs: A Survey. SIAM Review, Society for Industrial and Applied Mathematics, 2016, 58 (3), pp.445 - 460. ⟨10.1137/140978053⟩. ⟨hal-01388533⟩

Record views