  A graph $G$ is called a pairwise compatibility graph (PCG, for short) if it
admits a tuple $(T,w, d_{\min},d_{\max})$ of a tree $T$ whose leaf set is equal
to the vertex set of $G$, a non-negative edge weight $w$, and two non-negative
reals $d_{\min}\leq d_{\max}$ such that $G$ has an edge between two vertices
$u,v\in V$ if and only if the distance between the two leaves $u$ and $v$ in
the weighted tree $(T,w)$ is in the interval $[d_{\min}, d_{\max}]$. The tree
$T$ is also called a witness tree of the PCG $G$. The problem of testing if a
given graph is a PCG is not known to be NP-hard yet. To obtain a complete
characterization of PCGs is a wide open problem in computational biology and
graph theory. In literature, most witness trees admitted by known PCGs are
stars and caterpillars. In this paper, we give a complete characterization for
a graph to be a star-PCG (a PCG that admits a star as its witness tree), which
provides us the first polynomial-time algorithm for recognizing star-PCGs.
