  A graph $G = (V,E)$ is a double-threshold graph if there exist a
vertex-weight function $w \colon V \to \mathbb{R}$ and two real numbers
$\mathtt{lb}, \mathtt{ub} \in \mathbb{R}$ such that $uv \in E$ if and only if
$\mathtt{lb} \le \mathtt{w}(u) + \mathtt{w}(v) \le \mathtt{ub}$. In the
literature, those graphs are studied also as the pairwise compatibility graphs
that have stars as their underlying trees. We give a new characterization of
double-threshold graphs that relates them to bipartite permutation graphs.
Using the new characterization, we present a linear-time algorithm for
recognizing double-threshold graphs. Prior to our work, the fastest known
algorithm by Xiao and Nagamochi [Algorithmica 2020] ran in $O(n^{3} m)$ time,
where $n$ and $m$ are the numbers of vertices and edges, respectively.
