is the star pairwise compatibility graph defined by $(S, {\mathtt{w}}',{\mathtt{lb}},{\mathtt{ub}})$.

Let $G = (V,E)$ be a star pairwise compatibility graph defined by $(S, {\mathtt{w}}, {\mathtt{lb}}, {\mathtt{ub}})$, where the star $S$ has $c$ as its center. For each $v \in V$, we set ${\mathtt{w}}'(v) = {\mathtt{w}}(vc)$. Then, $G$ is the double-threshold graph defined by ${\mathtt{w}}'$, ${\mathtt{lb}}$, and ${\mathtt{ub}}$.

The *threshold dimension* of a graph $G = (V,E)$ is the minimum integer $k$ such that there are $k$ threshold graphs $G_{i} = (V, E_{i})$, $1 \le i \le k$, with $E = \bigcup_{1 \le i \le k} E_{i}$. A graph $G = (V,E)$ has *co-threshold dimension* $k$ if its complement $\overline{G}$ has threshold dimension $k$. Since the class of threshold graphs is closed under taking complements [@MahadevP1995], the co-threshold dimension of $G = (V,E)$ is the minimum integer $k$ such that there are $k$ threshold graphs $G_{i} = (V, E_{i})$, $1 \le i \le k$, with $E = \bigcap_{1 \le i \le k} E_{i}$.

\[lem:twothreshold\] Every double-threshold graph has co-threshold dimension at most $2$.

Let $G = (V,E)$ be a double-threshold graph defined by ${\mathtt{w}}\colon V \to {\mathbb{R}}$, and ${\mathtt{lb}}, {\mathtt{ub}}\in {\mathbb{R}}$. Let $E_{1}$ and $E_{2}$ be the following sets: $$\begin{aligned}
  E_{1} 