---
abstract: '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 as the pairwise compatibility graphs that have stars as their underlying trees. We give a new characterization of double-threshold graphs, which gives connections 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 \[COCOON 2018\] ran in $O(n^6)$ time, where $n$ is the number of vertices.'
author:
- Yusuke Kobayashi
- Yoshio Okamoto
- Yota Otachi
- Yushi Uno
bibliography:
- 'dtg.bib'
title: 'Linear-Time Recognition of Double-Threshold Graphs'
---

Introduction {#sec:introduction}
============

A graph is a *threshold graph* if there exist a vertex-weight function and a real number called a weight lower bound such that two vertices are adjacent in the graph if and only if the associated vertex weight sum is at least the weight lower bound. Threshold graphs and their generalizations are well studied because of their beautiful structures and applications in many areas [@MahadevP1995; @Golumbic04]. In particular, the edge-intersections of two threshold graphs, and their complements (i.e., the union of two threshold graphs) have attracted several researchers in the past, and recognition algorithms with running time $O(n^5)$ by Ma [@Ma93], $O(n^4)$ by Raschle and Simon [@RaschleS95], and $O(n^3)$ by Sterbini and Raschle [@SterbiniR98] have been developed, where $n$ is the number of vertices.

In this paper, we study the class of double-threshold graphs, which is a proper generalization of threshold graphs and a proper specialization of the graphs that are edge-intersections of two threshold graphs. A graph is a *double-threshold graph* if there exist a vertex-weight function and two real numbers called lower and upper bounds of weight such that two vertices are adjacent if and only if their weight sum is at least the lower bound and at most the upper bound. To the best of our knowledge, this natural generalization of threshold graphs was not studied until quite recently. In 2018, Xiao and Nagamochi [@XiaoN18] studied this graph class under the different name of “star pairwise compatibility graphs” and presented an $O(n^6)$-time recognition algorithm.

Our main result is to give a new characterization of double-threshold graphs that gives a simple linear-time recognition algorithm. We first show that every double-threshold graph is a permutation graph (but not vice versa) and that a bipartite graph is a double-threshold graph if and only if it is a permutation graph. These facts imply that many NP-hard graph problems are polynomial-time solvable on (bipartite or non-bipartite) double-threshold graphs. We then show that a graph is a double-threshold graph if and only if an auxiliary graph constructed from the original graph is a bipartite permutation graph. This characterization gives a linear-time algorithm for recognizing double-threshold graphs.

Recently, we have realized that Jamison and Sprague [@JamisonS19] have independently showed that all double-threshold graphs are permutation graphs and that all bipartite permutation graphs are double-threshold graphs. Their proofs are based on a vertex-ordering characterization of permutation graphs and a BFS structure of bipartite permutation graphs, while ours are direct transformations between vertex weights and permutation diagrams. Note that in their paper Jamison and Sprague [@JamisonS19] used the term *bi-threshold graphs* instead of double-threshold graphs. However, the name of “bi-threshold graphs” is already used[^1] by Hammer and Mahadev [@HammerM85] for a different generalization of threshold graphs (see below). Thus, even though “bi-threshold” would sound better and probably more appropriate, we would like to keep our term “double-threshold” in this paper.

#### Other generalizations of threshold graphs. {#other-generalizations-of-threshold-graphs. .unnumbered}

There are many other generalizations of threshold graphs such as threshold signed graphs [@BenzakenHW85], threshold tolerance graphs [@MonmaRT88], quasi-threshold graphs (also known as trivially perfect graphs) [@YanCC96], weakly threshold graphs [@Barrus18], and paired threshold graphs [@RavanmehrPBM18]. We omit the definitions of these graph classes and only note that some small graphs show that these classes are incomparable to the class of double-threshold graphs (e.g., $3K_{2}$ and bull for threshold signed graphs, $2K_{2}$ and bull for threshold tolerance graphs, $C_{4}$ and $2 K_{3}$ for quasi-threshold graphs, $2K_{2}$ and bull for weakly threshold graphs, $C_{4}$ and bull for paired threshold graphs[^2]). For the class of bithreshold graphs introduced by Hammer and Mahadev [@HammerM85] (not the one introduced by Jamison and Sprague [@JamisonS19]), we can use $3K_{2}$ and bull to show that this class is incomparable to the class of double-threshold graphs. It is known that $3K_{2}$ is not a bithreshold graph [@HammerMP93], while $3K_{2}$ is a double-threshold graph as we will show later (Lemma \[lem:biperm-&gt;dtg\]). We will also show later that bull is not a double-threshold graph (Lemma \[lem:mfis\_with\_order5\]). It is not difficult to see that bull is a bithreshold graph just by checking the definition in [@HammerMP93].

Note that the concept of double-threshold digraphs introduced by Hamburger et al. [@HamburgerMPSX18] is concerned with directed acyclic graphs defined from a generalization of semiorders involving two thresholds and not related to threshold graphs or double-threshold graphs.

#### Pairwise compatibility graphs. {#pairwise-compatibility-graphs. .unnumbered}

Motivated by uniform sampling from phylogenetic trees in bioinformatics, Kearney, Munro, and Phillips [@KearneyMP03] defined pairwise compatibility graphs. A graph $G=(V,E)$ is a *pairwise compatibility graph* if there exists a quadruple ($T$, ${\mathtt{w}}$, ${\mathtt{lb}}$, ${\mathtt{ub}}$), where $T$ is a tree, ${\mathtt{w}}\colon E(T) \to {\mathbb{R}}$, and ${\mathtt{lb}}, {\mathtt{ub}}\in {\mathbb{R}}$, such that the set of leaves in $T$ coincides with $V$ and $uv \in E$ if and only if the (weighted) distance $d_{T}(u, v)$ between $u$ and $v$ in $T$ satisfies ${\mathtt{lb}}\le d_{T}(u,v) \le {\mathtt{ub}}$.

Since its introduction, several authors have studied properties of pairwise compatibility graphs, but the existence of a polynomial-time recognition algorithm for that graph class has been open. The survey article by Calamoneri and Sinaimeri [@CalamoneriS16] proposed to look at the class of pairwise compatibility graphs defined on stars (i.e., star pairwise compatibility graphs), and asked for a characterization of star pairwise compatibility graphs. Recently, Xiao and Nagamochi [@XiaoN18] solved the open problem and gave an $O(n^6)$-time algorithm to recognize a star pairwise compatibility graph.

As we will see after the formal definition of double-threshold graphs, the star pairwise compatibility graphs are precisely the double-threshold graphs. Although the pairwise compatibility graphs are rather well studied, we study the double-threshold graphs in the context of threshold graphs and their generalizations. This is because, in our opinion, the double-threshold graphs and techniques used for them are more relevant in that context.

Preliminaries {#sec:preliminaries}
=============

All graphs in this paper are undirected, simple, and finite. A graph $G$ is given by the pair of its vertex set $V$ and its edge set $E$ as $G=(V,E)$. The vertex set and the edge set of $G$ are often denoted by $V(G)$ and $E(G)$, respectively. The *order* of a graph refers to the number of its vertices. For a vertex $v$ in a graph $G = (V,E)$, its *neighborhood* is the set of vertices that are adjacent to $v$, and denoted by $N_{G}(v) = \{ u \mid uv \in E\}$. When the graph $G$ is clear from the context, we often omit the subscript. A linear ordering $\prec$ on a set $S$ with $|S| = n$ can be represented by a sequence $\langle s_{1}, s_{2}, \dots, s_{n} \rangle$ of the elements in $S$, in which $s_{i} \prec s_{j}$ if and only if $i< j$. By abusing the notation, we sometimes write ${\prec} = \langle s_{1}, s_{2}, \dots, s_{n} \rangle$.

Double-threshold graphs
-----------------------

A graph $G=(V,E)$ is a *threshold graph* if there exist a vertex-weight function ${\mathtt{w}}\colon V \to {\mathbb{R}}$ and a real number ${\mathtt{lb}}\in {\mathbb{R}}$ with the following property: $$uv \in E \iff {\mathtt{lb}}\le {\mathtt{w}}(u) + {\mathtt{w}}(v).$$ A graph $G=(V,E)$ is a *double-threshold graph* if there exist a vertex-weight function ${\mathtt{w}}\colon V \to {\mathbb{R}}$ and two real numbers ${\mathtt{lb}}, {\mathtt{ub}}\in {\mathbb{R}}$ with the following property: $$uv \in E \iff {\mathtt{lb}}\le {\mathtt{w}}(u) + {\mathtt{w}}(v) \le {\mathtt{ub}}.$$ Then, we say that the double-threshold graph $G$ is *defined* by ${\mathtt{w}}$, ${\mathtt{lb}}$ and ${\mathtt{ub}}$.

The definition of a double-threshold graph can be understood visually in the plane. See [ \[fig:dtg\_example1\]]{} for an example. In the $xy$-plane, we consider the slab defined by $\{(x,y) \mid {\mathtt{lb}}\leq x+y \leq {\mathtt{ub}}\}$ that is illustrated in gray. Then, two vertices $u,v \in V$ are joined by an edge if and only if the point $({\mathtt{w}}(u),{\mathtt{w}}(v))$ lies in the slab.

![(Left) A double-threshold graph. The weight of each vertex is given as ${\mathtt{w}}(a)=1$, ${\mathtt{w}}(b)=3$, ${\mathtt{w}}(c)=5$, and ${\mathtt{w}}(d)=7$; the lower bound is ${\mathtt{lb}}=4$ and the upper bound is ${\mathtt{ub}}=8$. (Right) Understanding the definition in the $xy$-plane. A white dot represents the point $({\mathtt{w}}(u),{\mathtt{w}}(v))$ for distinct vertices $u,v$, and a cross represents a point $({\mathtt{w}}(v),{\mathtt{w}}(v))$ for a vertex $v$. Two distinct vertices $u$ and $v$ are joined by an edge if and only if the corresponding white dot lies in the gray slab. []{data-label="fig:dtg_example1"}](\figdir/dtg_example1)

Every threshold graph is a double-threshold graph as one can set a dummy upper bound ${\mathtt{ub}}> \max \{{\mathtt{w}}(u) + {\mathtt{w}}(v) \mid u,v \in V\}$. From the definition of double-threshold graphs, we can easily see that they coincide with the star pairwise compatibility graphs.

A graph is a double-threshold graph if and only if it is a star pairwise compatibility graph.

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}}$. We construct an edge-weighted star $S$ with the center $c$ and the leaf set $V$ such that the weight ${\mathtt{w}}'(vc)$ of each edge $vc \in E(S)$ is ${\mathtt{w}}(v)$. Then, $G$ 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} &= \{uv \mid u,v \in V, \; {\mathtt{lb}}\le {\mathtt{w}}(u) + {\mathtt{w}}(v)\}, \\
  E_{2} &= \{uv \mid u,v \in V, \; -{\mathtt{ub}}\le -{\mathtt{w}}(u) -{\mathtt{w}}(v)\}.\end{aligned}$$ It holds that $(V, E_{1})$ and $(V, E_{2})$ are threshold graphs and that $E_{1} \cap E_{2} = E$.

The next lemma allows us to use any values as ${\mathtt{lb}}$ and ${\mathtt{ub}}$ for defining a double-threshold graph. It also says that we do not have to consider degenerated cases, where some vertices have the same weight or some weight sum equals to the lower or upper bound.

\[lem:nice-representation\] 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}}$. For every pair $({\mathtt{lb}}^{*}, {\mathtt{ub}}^{*}) \in {\mathbb{R}}^{2}$ with ${\mathtt{lb}}^{*} < {\mathtt{ub}}^{*}$, there exists ${\mathtt{w}}^{*} \colon V \to {\mathbb{R}}$ defining $G$ with ${\mathtt{lb}}^{*}$ and ${\mathtt{ub}}^{*}$ such that

1.  $\{v \mid {\mathtt{lb}}/2 \le {\mathtt{w}}(v) \le {\mathtt{ub}}/2\} = \{v \mid {\mathtt{lb}}^{*}/2 \le {\mathtt{w}}^{*}(v) \le {\mathtt{ub}}^{*}/2\}$,

2.  ${\mathtt{w}}^{*}(u) + {\mathtt{w}}^{*}(v) \notin \{{\mathtt{lb}}^{*}, {\mathtt{ub}}^{*}\}$ for all $(u,v) \in V^{2}$, and

3.  ${\mathtt{w}}^{*}(u) \ne {\mathtt{w}}^{*}(v)$ if $u \ne v$.

If $G$ has no edge, then the lemma trivially holds. Thus, we assume that $G$ has at least one edge. This implies that ${\mathtt{lb}}\le {\mathtt{ub}}$.

\[clm:nicer-rep1\] There exist ${\mathtt{lb}}', {\mathtt{ub}}' \in {\mathbb{R}}$ with ${\mathtt{lb}}' < {\mathtt{ub}}'$ such that ${\mathtt{w}}$, ${\mathtt{lb}}'$, and ${\mathtt{ub}}'$ define $G$, $\{v \mid {\mathtt{lb}}/2 \le {\mathtt{w}}(v) \le {\mathtt{ub}}/2\} = \{v \mid {\mathtt{lb}}'/2 \le {\mathtt{w}}(v) \le {\mathtt{ub}}'/2\}$, and ${\mathtt{w}}(u) + {\mathtt{w}}(v) \notin \{{\mathtt{lb}}', {\mathtt{ub}}'\}$ for all $(u,v) \in V^{2}$.

Claim \[clm:nicer-rep1\] is illustrated by [ \[fig:claim2-4\]]{}.

![Proof of Claim \[clm:nicer-rep1\]. (Left) There is a pair $(u,v)$ of vertices such that ${\mathtt{w}}(u)+{\mathtt{w}}(v)={\mathtt{ub}}$. The values $\alpha$ and $\beta$ are shown in red and blue, respectively. (Right) The bounds ${\mathtt{lb}}, {\mathtt{ub}}$ are replaced by ${\mathtt{lb}}', {\mathtt{ub}}'$.[]{data-label="fig:claim2-4"}](\figdir/claim2-4)

\[Proof of Claim \[clm:nicer-rep1\]\] If ${\mathtt{w}}(v) \ge {\mathtt{lb}}/2$ for all $v \in V$, then we set ${\mathtt{lb}}'$ to an arbitrary value smaller than ${\mathtt{lb}}$. Similarly, if ${\mathtt{w}}(v) \le {\mathtt{ub}}/2$ for all $v \in V$, then we use any value larger than ${\mathtt{ub}}$ as ${\mathtt{ub}}'$. Since we are done in these cases, we assume that there exists a vertex with weight less than ${\mathtt{lb}}/2$, and there exists a vertex with weight more than ${\mathtt{ub}}/2$.

Let $\alpha, \beta \in {\mathbb{R}}$ be the following values: $$\begin{aligned}
{2}
  \alpha &= \max&\{{\mathtt{w}}(u) + {\mathtt{w}}(v) \mid (u,v) \in V^{2} \text{ such that } {\mathtt{w}}(u) + {\mathtt{w}}(v) < {\mathtt{lb}}\},
  \\
  \beta  &= \min&\{{\mathtt{w}}(u) + {\mathtt{w}}(v) \mid (u,v) \in V^{2} \text{ such that } {\mathtt{w}}(u) + {\mathtt{w}}(v) > {\mathtt{ub}}\}.\end{aligned}$$ We set ${\mathtt{lb}}' = ({\mathtt{lb}}+ \alpha)/2$ and ${\mathtt{ub}}' = ({\mathtt{ub}}+ \beta)/2$. Then, $\alpha < {\mathtt{lb}}' < {\mathtt{lb}}\le {\mathtt{ub}}< {\mathtt{ub}}' < \beta$, and thus ${\mathtt{lb}}' < {\mathtt{ub}}'$. We can see that ${\mathtt{lb}}'$ and ${\mathtt{ub}}'$ satisfy the other conditions in the claim as follows. Let $(u,v) \in V^{2}$. If ${\mathtt{lb}}\le {\mathtt{w}}(u) + {\mathtt{w}}(v) \le {\mathtt{ub}}$, then ${\mathtt{lb}}' < {\mathtt{w}}(u) + {\mathtt{w}}(v) < {\mathtt{ub}}'$. If ${\mathtt{w}}(u) + {\mathtt{w}}(v) < {\mathtt{lb}}$, then ${\mathtt{w}}(u) + {\mathtt{w}}(v) \le \alpha < {\mathtt{lb}}'$. If ${\mathtt{w}}(u) + {\mathtt{w}}(v) > {\mathtt{ub}}$, then ${\mathtt{w}}(u) + {\mathtt{w}}(v) \ge \beta > {\mathtt{ub}}'$. This implies that ${\mathtt{w}}$, ${\mathtt{lb}}'$, and ${\mathtt{ub}}'$ define $G$, that $\{v \mid {\mathtt{lb}}/2 \le {\mathtt{w}}(v) \le {\mathtt{ub}}/2\} = \{v \mid {\mathtt{lb}}'/2 \le {\mathtt{w}}(v) \le {\mathtt{ub}}'/2\}$, and that ${\mathtt{w}}(u) + {\mathtt{w}}(v) \not\in \{{\mathtt{lb}}',{\mathtt{ub}}'\}$ for all $(u, v) \in V^{2}$.

In the following, let ${\mathtt{lb}}'$ and ${\mathtt{ub}}'$ be the bounds in Claim \[clm:nicer-rep1\].

\[clm:nicer-rep2\] There exists ${\mathtt{w}}' \colon V \to {\mathbb{R}}$ such that ${\mathtt{w}}'$, ${\mathtt{lb}}'$, and ${\mathtt{ub}}'$ define $G$, $\{v \mid {\mathtt{lb}}/2 \le {\mathtt{w}}(v) \le {\mathtt{ub}}/2\} = \{v \mid {\mathtt{lb}}'/2 \le {\mathtt{w}}'(v) \le {\mathtt{ub}}'/2\}$, ${\mathtt{w}}'(u) + {\mathtt{w}}'(v) \notin \{{\mathtt{lb}}', {\mathtt{ub}}'\}$ for all $(u,v) \in V^{2}$, and ${\mathtt{w}}'(u) \ne {\mathtt{w}}'(v)$ if $u \ne v$.

Claim \[clm:nicer-rep2\] is illustrated by [ \[fig:claim2-5\]]{}.

![Proof of Claim \[clm:nicer-rep2\]. (Left) The second smallest weight is shared by two vertices $z$ and $z'$. (Right) The weight of $z$ is changed, but the double-threshold graph does not change.[]{data-label="fig:claim2-5"}](\figdir/claim2-5){width="\textwidth"}

\[Proof of Claim \[clm:nicer-rep2\]\] Let ${\mathtt{w}}'\colon V \to {\mathbb{R}}$ be a vertex-weight function such that ${\mathtt{w}}'$, ${\mathtt{lb}}'$, and ${\mathtt{ub}}'$ define $G$, $\{v \mid {\mathtt{lb}}/2 \le {\mathtt{w}}(v) \le {\mathtt{ub}}/2\} = \{v \mid {\mathtt{lb}}'/2 \le {\mathtt{w}}'(v) \le {\mathtt{ub}}'/2\}$, ${\mathtt{w}}'(u) + {\mathtt{w}}'(v) \notin \{{\mathtt{lb}}', {\mathtt{ub}}'\}$ for all $(u,v) \in V^{2}$, and, under these conditions, the number $|\{v \mid {\mathtt{w}}'(v) \ne {\mathtt{w}}'(u) \text{ for all } u \in V \setminus \{v\} \}|$ of unique-weight vertices is maximum. Such ${\mathtt{w}}'$ exists since ${\mathtt{w}}$ itself satisfies all the conditions.

Suppose to the contrary that there are distinct vertices $z, z' \in V$ with the same weight ${\mathtt{w}}'(z) = {\mathtt{w}}'(z')$. Let $\alpha, \beta, \gamma$ be defined as follows: $$\begin{aligned}
\alpha &=&
\begin{cases}
\min \{ {\mathtt{w}}'(v) \mid v \in N(z) \} & \text{if } N(z) \ne \emptyset,\\
+\infty & \text{otherwise};
\end{cases}\\
\beta &=&
\begin{cases}
\min \{ {\mathtt{w}}'(v) \mid v \notin N(z), \; {\mathtt{w}}'(z) + {\mathtt{w}}'(v) > {\mathtt{ub}}' \}
 & \text{if } \{v \notin N(z) \mid {\mathtt{w}}'(z) + {\mathtt{w}}'(v) > {\mathtt{ub}}'\} \ne \emptyset,\\
+\infty & \text{otherwise};
\end{cases}\\
\gamma &=&
\begin{cases}
\max \{ {\mathtt{w}}'(v) \mid {\mathtt{w}}'(v) < {\mathtt{w}}'(z) \} & \text{if there exists } v \text{ such that } {\mathtt{w}}'(v) < {\mathtt{w}}'(z),\\
-\infty & \text{otherwise}.
\end{cases}\end{aligned}$$ Let $$\varepsilon = \min\{{\mathtt{w}}'(z) + \alpha - {\mathtt{lb}}', {\mathtt{w}}'(z) + \beta - {\mathtt{ub}}', {\mathtt{w}}'(z) - \gamma, 
    |{\mathtt{w}}'(z) - {\mathtt{lb}}'/2|, |{\mathtt{w}}'(z) - {\mathtt{ub}}'/2|\}.$$ Note that $\varepsilon$ is positive and not infinitely large. By decreasing the weight of $z$ by $\varepsilon/2$, we define ${\mathtt{w}}''$. That is, ${\mathtt{w}}''(z) = {\mathtt{w}}'(z) - \varepsilon/2$ and ${\mathtt{w}}''(v) = {\mathtt{w}}'(v)$ for all other $v \ne z$.

Observe that $z$ has a unique weight under ${\mathtt{w}}''$ because $z$ is the only vertex of weight in the interval $(\gamma, {\mathtt{w}}'(z))$. Since all vertices other than $z$ have the same weight in ${\mathtt{w}}'$ and ${\mathtt{w}}''$, the number of unique-weight vertices under ${\mathtt{w}}''$ is larger than the one under ${\mathtt{w}}'$.

Next we show that ${\mathtt{w}}''(z) + {\mathtt{w}}''(v) \notin \{{\mathtt{lb}}',{\mathtt{ub}}'\}$ for all $v \in V$ and that ${\mathtt{w}}''$, ${\mathtt{lb}}'$, and ${\mathtt{ub}}'$ define $G$. Let $v \in V$. (Note that $v$ may be $z$.) By the assumption on ${\mathtt{w}}'$, we have ${\mathtt{w}}'(z) + {\mathtt{w}}'(v) \notin \{{\mathtt{lb}}', {\mathtt{ub}}'\}$. If ${\mathtt{w}}'(z) + {\mathtt{w}}'(v) < {\mathtt{lb}}'$, then ${\mathtt{w}}''(z) + {\mathtt{w}}''(v) < {\mathtt{lb}}'$ holds as ${\mathtt{w}}''(z) < {\mathtt{w}}'(z)$ and ${\mathtt{w}}''(v) = {\mathtt{w}}'(v)$. Similarly, if ${\mathtt{w}}'(z) + {\mathtt{w}}'(v) < {\mathtt{ub}}'$, then ${\mathtt{w}}''(z) + {\mathtt{w}}''(v) < {\mathtt{ub}}'$. Assume that ${\mathtt{w}}'(z) + {\mathtt{w}}'(v) > {\mathtt{lb}}'$. If $v$ is a neighbor of $z$, then ${\mathtt{w}}'(v) \ge \alpha$ holds, and thus ${\mathtt{w}}''(z) + {\mathtt{w}}''(v) > {\mathtt{lb}}'$ as follows: $$\begin{aligned}
  {\mathtt{w}}''(z) + {\mathtt{w}}''(v)
  &= {\mathtt{w}}'(z) + {\mathtt{w}}'(v) - \varepsilon/2 
  \\
  &\ge {\mathtt{w}}'(z) + {\mathtt{w}}'(v) - ({\mathtt{w}}'(z) + \alpha - {\mathtt{lb}}')/2 
  \\
  &\ge {\mathtt{w}}'(z) + {\mathtt{w}}'(v) - ({\mathtt{w}}'(z) + {\mathtt{w}}'(v) - {\mathtt{lb}}')/2 
  \\
  &= ({\mathtt{w}}'(z) + {\mathtt{w}}'(v) + {\mathtt{lb}}')/2
  \\
  &> ({\mathtt{lb}}' + {\mathtt{lb}}')/2
  \\
  &= {\mathtt{lb}}'.\end{aligned}$$ If $v = z$, then ${\mathtt{w}}'(z) = {\mathtt{w}}'(v) > {\mathtt{lb}}'/2$, and thus $$\begin{aligned}
  {\mathtt{w}}''(z) + {\mathtt{w}}''(v)
  &= 2{\mathtt{w}}'(z) - \varepsilon
  \\
  &\ge 2{\mathtt{w}}'(z) - |{\mathtt{w}}'(z) - {\mathtt{lb}}'/2|
  = 2{\mathtt{w}}'(z) - ({\mathtt{w}}'(z) - {\mathtt{lb}}'/2)
  \\
  &= {\mathtt{w}}'(z) + {\mathtt{lb}}'/2
  \\
  &> {\mathtt{lb}}'.\end{aligned}$$ Next, assume that ${\mathtt{w}}'(z) + {\mathtt{w}}'(v) > {\mathtt{ub}}'$. If $v$ is a non-neighbor of $z$, then ${\mathtt{w}}'(v) \ge \beta$. Thus, ${\mathtt{w}}''(z) + {\mathtt{w}}''(v) > {\mathtt{ub}}'$ holds as follows: $$\begin{aligned}
  {\mathtt{w}}''(z) + {\mathtt{w}}''(v)
  &= 
  {\mathtt{w}}'(z) + {\mathtt{w}}'(v) - \varepsilon/2 
  \\
  &\ge {\mathtt{w}}'(z) + {\mathtt{w}}'(v) - ({\mathtt{w}}'(z) + \beta - {\mathtt{ub}}')/2 
  \\
  &\ge {\mathtt{w}}'(z) + {\mathtt{w}}'(v) - ({\mathtt{w}}'(z) + {\mathtt{w}}'(v) - {\mathtt{ub}}')/2 
  \\
  &= ({\mathtt{w}}'(z) + {\mathtt{w}}'(v) + {\mathtt{ub}}')/2
  \\
  &> ({\mathtt{ub}}' + {\mathtt{ub}}')/2 
  \\
  &= {\mathtt{ub}}'.\end{aligned}$$ If $v = z$, then ${\mathtt{w}}'(z) = {\mathtt{w}}'(v) > {\mathtt{ub}}'/2$, and thus $$\begin{aligned}
  {\mathtt{w}}''(z) + {\mathtt{w}}''(v)
  &= 2{\mathtt{w}}'(z) - \varepsilon
  \\
  &\ge 2{\mathtt{w}}'(z) - |{\mathtt{w}}'(z) - {\mathtt{ub}}'/2|
  = 2{\mathtt{w}}'(z) - ({\mathtt{w}}'(z) - {\mathtt{ub}}'/2)
  \\
  &= {\mathtt{w}}'(z) + {\mathtt{ub}}'/2
  \\
  &> {\mathtt{ub}}'.\end{aligned}$$

Finally, we show that $\{v \mid {\mathtt{lb}}/2 \le {\mathtt{w}}(v) \le {\mathtt{ub}}/2\} = \{v \mid {\mathtt{lb}}'/2 \le {\mathtt{w}}''(v) \le {\mathtt{ub}}'/2\}$. To this end, it suffices to show that ${\mathtt{lb}}'/2 < {\mathtt{w}}'(z) < {\mathtt{ub}}'/2$ if and only if ${\mathtt{lb}}'/2 < {\mathtt{w}}''(z) < {\mathtt{ub}}'/2$ as $2{\mathtt{w}}'(z), 2{\mathtt{w}}''(z) \notin \{{\mathtt{lb}}', {\mathtt{ub}}'\}$. If ${\mathtt{lb}}'/2 < {\mathtt{w}}'(z) < {\mathtt{ub}}'/2$, then ${\mathtt{w}}''(z) < {\mathtt{w}}'(z) < {\mathtt{ub}}'/2$ and $${\mathtt{w}}''(z)
  = {\mathtt{w}}'(z) - \varepsilon/2 
  > {\mathtt{w}}'(z) - \varepsilon
  \ge  {\mathtt{w}}'(z) - |{\mathtt{w}}'(z) - {\mathtt{lb}}'/2| 
  = {\mathtt{w}}'(z) - ({\mathtt{w}}'(z) - {\mathtt{lb}}'/2) 
  = {\mathtt{lb}}'/2.$$ If ${\mathtt{w}}'(z) < {\mathtt{lb}}'/2$, then ${\mathtt{w}}''(z) < {\mathtt{w}}'(z) < {\mathtt{lb}}'/2$. If ${\mathtt{w}}'(z) > {\mathtt{ub}}'/2$, then we have $${\mathtt{w}}''(z)
  = {\mathtt{w}}'(z) - \varepsilon/2 
  > {\mathtt{w}}'(z) - \varepsilon
  \ge {\mathtt{w}}'(z) - |{\mathtt{w}}'(z) - {\mathtt{ub}}'/2|
  = {\mathtt{w}}'(z) - ({\mathtt{w}}'(z) - {\mathtt{ub}}'/2) 
  = {\mathtt{ub}}'/2.$$

We have shown that ${\mathtt{w}}''$, ${\mathtt{lb}}'$, and ${\mathtt{ub}}'$ define $G$, $\{v \mid {\mathtt{lb}}/2 \le {\mathtt{w}}(v) \le {\mathtt{ub}}/2\} = \{v \mid {\mathtt{lb}}'/2 \le {\mathtt{w}}''(v) \le {\mathtt{ub}}'/2\}$, and ${\mathtt{w}}''(u) + {\mathtt{w}}''(v) \notin \{{\mathtt{lb}}', {\mathtt{ub}}'\}$ for all $(u,v) \in V^{2}$. We also showed that the number of unique-weight vertices under ${\mathtt{w}}''$ is larger than the one under ${\mathtt{w}}'$. This contradicts the assumption on how ${\mathtt{w}}'$ is chosen, and thus we can conclude that no two vertices have the same weight in ${\mathtt{w}}'$.

We continue the proof of Lemma \[lem:nice-representation\]. Let ${\mathtt{w}}'$ be the vertex-weight function in Claim \[clm:nicer-rep2\]. Given ${\mathtt{lb}}^{*}, {\mathtt{ub}}^{*} \in {\mathbb{R}}$ with ${\mathtt{lb}}^{*} < {\mathtt{ub}}^{*}$, let $\rho = ({\mathtt{ub}}^{*} - {\mathtt{lb}}^{*})/({\mathtt{ub}}' - {\mathtt{lb}}')$. For each $v \in V$, we set ${\mathtt{w}}^{*}(v) = \rho \cdot {\mathtt{w}}'(v) - \left(\rho \cdot {\mathtt{lb}}' - {\mathtt{lb}}^{*}\right)/2$. Then, ${\mathtt{w}}^{*}(u) \ne {\mathtt{w}}^{*}(v)$ if $u \ne v$. Now for each $(u,v) \in V^{2}$, $$\begin{aligned}
  & {\mathtt{lb}}^{*} < {\mathtt{w}}^{*}(u) + {\mathtt{w}}^{*}(v) < {\mathtt{ub}}^{*}
  \\
  &\iff {\mathtt{lb}}^{*}
  <
  \rho \cdot ({\mathtt{w}}'(u) + {\mathtt{w}}'(v))
  - \left(\rho \cdot {\mathtt{lb}}' - {\mathtt{lb}}^{*}\right)
  <
  {\mathtt{ub}}^{*}
  \\
  &\iff \rho \cdot {\mathtt{lb}}'
  <
  \rho \cdot ({\mathtt{w}}'(u) + {\mathtt{w}}'(v))
  <
  \rho \cdot {\mathtt{lb}}' + {\mathtt{ub}}^{*} - {\mathtt{lb}}^{*}
  = \rho \cdot {\mathtt{lb}}'  + \rho \cdot ({\mathtt{ub}}' - {\mathtt{lb}}')
  \\
  &\iff {\mathtt{lb}}' 
  <
  {\mathtt{w}}'(u) + {\mathtt{w}}'(v)
  <
  {\mathtt{ub}}'.\end{aligned}$$ Similarly, ${\mathtt{w}}^{*}(u) + {\mathtt{w}}^{*}(v) < {\mathtt{lb}}^{*}$ if and only if ${\mathtt{w}}'(u) + {\mathtt{w}}'(v) < {\mathtt{lb}}'$, and ${\mathtt{w}}^{*}(u) + {\mathtt{w}}^{*}(v) > {\mathtt{ub}}^{*}$ if and only if ${\mathtt{w}}'(u) + {\mathtt{w}}'(v) > {\mathtt{ub}}'$. Since ${\mathtt{w}}'(u) + {\mathtt{w}}'(v) \notin \{{\mathtt{lb}}', {\mathtt{ub}}'\}$ for all $(u,v)\in V^{2}$, it follows that ${\mathtt{w}}^{*}$, ${\mathtt{lb}}^{*}$, and ${\mathtt{ub}}^{*}$ define $G$, $\{v \mid {\mathtt{lb}}/2 \le {\mathtt{w}}(v) \le {\mathtt{ub}}/2\} = \{v \mid {\mathtt{lb}}^{*}/2 \le {\mathtt{w}}^{*}(v) \le {\mathtt{ub}}^{*}/2\}$, and ${\mathtt{w}}^{*}(u) + {\mathtt{w}}^{*}(v) \notin \{{\mathtt{lb}}^{*}, {\mathtt{ub}}^{*}\}$ for all $(u,v)\in V^{2}$.

The following lemma can be proved using a characterization of graphs of co-threshold dimension at most 2 [@RaschleS95]. Also, a proof of the same fact was given by Xiao and Nagamochi [@XiaoN18] using their characterization of double-threshold graphs. To make the discussion self-contained, we present a direct proof here.

\[lem:at-most-one-nonbipartite\] A double-threshold graph has at most one non-bipartite component.

Let $G$ be a double-threshold graph defined by ${\mathtt{w}}\colon V\to {\mathbb{R}}$ and ${\mathtt{lb}}, {\mathtt{ub}}\in {\mathbb{R}}$. It suffices to show that all cycles of odd lengths in $G$ belong to the same component.

Let $C$ and $C'$ be two induced cycles in $G$ that are vertex-disjoint and of odd lengths. Since $C$ is of odd length, we can find three vertices $a$, $b$, $c$ that consecutively appear in $C$ such that ${\mathtt{w}}(a) \le {\mathtt{w}}(b) \le {\mathtt{w}}(c)$. Similarly, we can find three consecutive vertices $x$, $y$, $z$ in $C'$ such that ${\mathtt{w}}(x) \le {\mathtt{w}}(y) \le {\mathtt{w}}(z)$. By symmetry, we may assume that ${\mathtt{w}}(b) \le {\mathtt{w}}(y)$. This implies that ${\mathtt{w}}(a) \le {\mathtt{w}}(y)$ and ${\mathtt{w}}(b) \le {\mathtt{w}}(z)$. Since $ab$ and $yz$ are edges, we have ${\mathtt{lb}}\le {\mathtt{w}}(a) + {\mathtt{w}}(b) \le {\mathtt{w}}(y) + {\mathtt{w}}(b) \le {\mathtt{w}}(y) + {\mathtt{w}}(z) \le {\mathtt{ub}}$. This implies that $by$ is also an edge, and thus $C$ and $C'$ belong to the same component.

We further observe that bipartite components can be considered separately. A bipartite graph is denoted by $(X, Y; E)$ when its vertex set is partitioned into two independent sets $X$ and $Y$ and its edge set is $E$.

\[lem:disjoint-bicomponent\] The disjoint union of a double-threshold graph and a bipartite double-threshold graph is a double-threshold graph.

Let $G = (V, E_{G})$ be a double-threshold graph defined by ${\mathtt{w}}_{G} \colon V \to {\mathbb{R}}$ and ${\mathtt{lb}}, {\mathtt{ub}}\in {\mathbb{R}}$. Let $H = (X,Y; E_{H})$ be a bipartite double-threshold graph. By Lemma \[lem:nice-representation\], we may assume that ${\mathtt{lb}}< {\mathtt{ub}}$ and $H$ is defined by the same ${\mathtt{lb}}$ and ${\mathtt{ub}}$ with some weight function ${\mathtt{w}}_{H} \colon X \cup Y \to {\mathbb{R}}$.

We set $\alpha \in {\mathbb{R}}_{\ge 0}$ large enough so that the following conditions hold: $$\begin{aligned}
  {\mathtt{ub}}&< 2 \cdot \min\{ \min\{{\mathtt{w}}_{G}(v) \mid v \in V\}, \min\{{\mathtt{w}}_{H}(w) \mid w \in X \cup Y \}\} + \alpha, \\
  {\mathtt{lb}}&> 2 \cdot \max\{ \max\{{\mathtt{w}}_{G}(v) \mid v \in V\}, \max\{{\mathtt{w}}_{H}(w) \mid w \in X \cup Y \}\} - \alpha.\end{aligned}$$ Now, we set ${\mathtt{w}}\colon (V \cup X \cup Y) \to {\mathbb{R}}$ as follows: $${\mathtt{w}}(w) = 
  \begin{cases}
    {\mathtt{w}}_{G}(w)     & \text{if } w \in V, \\
    {\mathtt{w}}_{H}(w) + \alpha & \text{if } w \in X, \\
    {\mathtt{w}}_{H}(w) - \alpha & \text{if } w \in Y.
  \end{cases}$$

We show that ${\mathtt{w}}$, ${\mathtt{lb}}$, and ${\mathtt{ub}}$ define the disjoint union $(V \cup X \cup Y, E_{G} \cup E_{H})$ of $G$ and $H$. For two vertices $u,v \in V$, we have ${\mathtt{w}}(u) + {\mathtt{w}}(v) = {\mathtt{w}}_{G}(u) + {\mathtt{w}}_{G}(v)$. Similarly, for $x \in X$ and $y \in Y$, we have ${\mathtt{w}}(x) + {\mathtt{w}}(y) = {\mathtt{w}}_{H}(x) + {\mathtt{w}}_{H}(y)$. For $x_{1}, x_{2} \in X$, we have ${\mathtt{w}}(x_{1}) + {\mathtt{w}}(x_{2}) = {\mathtt{w}}_{H}(x_{1}) + {\mathtt{w}}_{H}(x_{2}) + 2\alpha > {\mathtt{ub}}$. For $y_{1}, y_{2} \in Y$, we have ${\mathtt{w}}(y_{1}) + {\mathtt{w}}(y_{2}) = {\mathtt{w}}_{H}(y_{1}) + {\mathtt{w}}_{H}(y_{2}) - 2\alpha < {\mathtt{lb}}$. For $v \in V$ and $x \in X$, we have ${\mathtt{w}}(v) + {\mathtt{w}}(x) = {\mathtt{w}}_{G}(v) + {\mathtt{w}}_{H}(x) + \alpha > {\mathtt{ub}}$. Finally, for $v \in V$ and $y \in Y$, we have ${\mathtt{w}}(v) + {\mathtt{w}}(y) = {\mathtt{w}}_{G}(v) + {\mathtt{w}}_{H}(y) - \alpha < {\mathtt{lb}}$.

By Lemmas \[lem:at-most-one-nonbipartite\] and \[lem:disjoint-bicomponent\], we have the following corollary.

\[cor:component\] A graph is a double-threshold graph if and only if it contains at most one non-bipartite component and all components are double-threshold graphs.

Permutation graphs
------------------

A graph $G=(V,E)$ is a *permutation graph* if there exist linear orderings $\prec_1, \prec_2$ on $V$ with the following property: $$uv \in E \iff (u \prec_1 v \text{ and } v \prec_2 u) \text{ or } (u \prec_2 v \text{ and } v \prec_1 u).$$ We say that $\prec_{1}$ and $\prec_{2}$ *define* the permutation graph $G$. We call $\prec_{1}$ a *permutation ordering* of $G$ if there exists a linear ordering $\prec_{2}$ satisfying the condition above. Since $\prec_{1}$ and $\prec_{2}$ play a symmetric role in the definition, $\prec_{2}$ is also a permutation ordering of $G$. Note that for a graph $G$ and a permutation ordering $\prec_{1}$ of $G$, the other ordering $\prec_{2}$ that defines $G$ together with $\prec_{1}$ is uniquely determined. Also note that if $\prec_{1}$ and $\prec_{2}$ define $G$, then $\prec_{1}^{\mathrm{R}}$ and $\prec_{2}^{\mathrm{R}}$ also define $G$, where $\prec^{\mathrm{R}}$ denotes the reversed ordering of $\prec$.

We often represent a permutation graph with a *permutation diagram*, which is drawn as follows. See [ \[fig:permdia\_example1\]]{} for an illustration. Imagine two horizontal parallel lines $\ell_1$ and $\ell_2$ on the plane. Then, we place the vertices in $V$ on $\ell_1$ from left to right according to the permutation ordering $\prec_1$ as distinct points, and similarly place the vertices in $V$ on $\ell_2$ from left to right according to $\prec_2$ as distinct points. The positions of $v\in V$ can be represented by $x$-coordinates on $\ell_{1}$ and $\ell_{2}$, which are denoted by ${\mathtt{x}}_{1}(v)$ and ${\mathtt{x}}_{2}(v)$, respectively. We connect the two points representing the same vertex with a line segment. The process results in a diagram with $|V|$ line segments. By definition, $uv \in E$ if and only if the line segments representing $u$ and $v$ cross in the permutation diagram, which is equivalent to the inequality $({\mathtt{x}}_1(u)-{\mathtt{x}}_1(v)) ({\mathtt{x}}_2(u)-{\mathtt{x}}_2(v)) < 0$.

![An example of a permutation diagram. (Left) A permutation graph $G$. (Right) A permutation diagram that represents $G$.[]{data-label="fig:permdia_example1"}](\figdir/permdia_example1)

Conversely, from a permutation diagram of $G$, we can extract linear orderings $\prec_{1}$ and $\prec_{2}$ as $$\begin{aligned}
{\mathtt{x}}_1(u) < {\mathtt{x}}_1(v) &\iff& u \prec_{1} v,\\
{\mathtt{x}}_2(u) < {\mathtt{x}}_2(v) &\iff& u \prec_{2} v.\end{aligned}$$ When those conditions are satisfied, we say that the orderings of the $x$-coordinates on $\ell_1$ and $\ell_2$ are *consistent* with the linear orderings $\prec_{1}$ and $\prec_{2}$, respectively.

A graph is a *bipartite permutation graph* if it is a bipartite graph and a permutation graph. Although a permutation graph may have an exponential number of permutation orderings, it is essentially unique for a connected bipartite permutation graph in the sense of Lemma \[lem:uniquerep\] below. For a graph $G = (V,E)$, linear orderings $\langle v_{1}, \dots, v_{n} \rangle$ and $\langle v'_{1}, \dots, v'_{n} \rangle$ on $V$ are *neighborhood-equivalent* if $N(v_{i}) = N(v'_{i})$ for all $i$.

\[[@HeggernesHMV15]\] \[lem:uniquerep\] Let $G$ be a connected bipartite permutation graph defined by $\prec_{1}$ and $\prec_{2}$. Then, every permutation ordering of $G$ is neighborhood-equivalent to $\prec_{1}$, $\prec_{2}$, $\prec_{1}^{\mathrm{R}}$, or $\prec_{2}^{\mathrm{R}}$.

A bipartite graph $(X,Y;E)$ is a *unit interval bigraph* if there is a set of unit intervals $\{I_{v} = [l_{v}, l_{v}+1] \mid v \in X \cup Y\}$ such that $xy \in E$ if and only if $I_{x} \cap I_{y} \ne \emptyset$ for $x \in X$ and $y \in Y$. The class of unit interval bigraphs is known to be equal to the class of bipartite permutation graphs.

\[[@SenS94; @West98; @HellH04]\] \[prop:bpg=uib\] A graph is a bipartite permutation graph if and only if it is a unit interval bigraph.

The following lemma shows that a bipartite permutation graph can be represented by a permutation diagram with a special property. An illustration is given in [ \[fig:lem2-11\]]{}.

![An illustration of Lemma \[lem:rightanglerep\]. (Left) A permutation diagram of a bipartite permutation graph $G=(X,Y;E)$. The vertices in $X$ are represented by blue segments, and the vertices in $Y$ are represented by red segments. (Right) A permutation diagram that represents $G$ obtained by Lemma \[lem:rightanglerep\].[]{data-label="fig:lem2-11"}](\figdir/lem2-11)

\[lem:rightanglerep\] Let $G=(X, Y; E)$ be a bipartite permutation graph. Then, $G$ can be represented by a permutation diagram in which ${\mathtt{x}}_{2}(x)={\mathtt{x}}_{1}(x)+1$ for $x \in X$ and ${\mathtt{x}}_{2}(y)={\mathtt{x}}_{1}(y)-1$ for $y \in Y$.

By Proposition \[prop:bpg=uib\], there is a set of unit intervals $\{I_{v} = [l_{v}, l_{v}+1] \mid v \in X \cup Y\}$ such that for $x \in X$ and $y \in Y$, $xy \in E$ if and only if $I_{x} \cap I_{y} \ne \emptyset$. We can assume that all endpoints of the intervals are distinct; that is, $l_{u} \notin \{l_{v}, l_{v}+1\}$ for all $u,v \in X \cup Y $ with $u \ne v$ [@West98]. For each $x \in X$, we set ${\mathtt{x}}_{1}(x) = l_{x}$ and ${\mathtt{x}}_{2}(x) = l_{x} + 1$. For each $y \in Y$, we set ${\mathtt{x}}_{1}(y) = l_{y}+1$ and ${\mathtt{x}}_{2}(y) = l_{y}$. It suffices to show that this permutation diagram represents $G$. Observe that line segments corresponding to vertices from the same set, $X$ or $Y$, are parallel and thus do not cross. For $x \in X$ and $y \in Y$, we have $$\begin{aligned}
  I_{x} \cap I_{y} \ne \emptyset
  &\iff
  |l_{x} - l_{y}| < 1 && (\because \text{ all endpoints are distinct})
  \\
  &\iff
  l_{x} < l_{y} + 1 \textrm{ and } l_{y} < l_{x} + 1
  \\
  &\iff
  {\mathtt{x}}_{1}(x) < {\mathtt{x}}_{1}(y) \textrm{ and } {\mathtt{x}}_{2}(y) < {\mathtt{x}}_{2}(x) && (\because x \in X, \  y \in Y)
  \\
  &\iff
  ({\mathtt{x}}_{1}(x)-{\mathtt{x}}_{1}(y)) ({\mathtt{x}}_{2}(x)-{\mathtt{x}}_{2}(y)) < 0.\end{aligned}$$ To see the last equivalence, observe that ${\mathtt{x}}_{1}(x) < {\mathtt{x}}_{2}(x)$ and ${\mathtt{x}}_{2}(y) < {\mathtt{x}}_{1}(y)$, and thus it is impossible to have both ${\mathtt{x}}_1(x) > {\mathtt{x}}_1(y)$ and ${\mathtt{x}}_2(y) > {\mathtt{x}}_2(x)$. Therefore, we conclude that the diagram represents $G$.

We can show that given a permutation ordering, there exists a permutation diagram consistent with the ordering that satisfies the conditions in Lemma \[lem:rightanglerep\].

\[cor:rightanglerep\] Let $G=(X, Y; E)$ be a connected bipartite permutation graph defined by permutation orderings $\prec_{1}$ and $\prec_{2}$. If the first vertex in $\prec_{1}$ belongs to $X$, then $G$ can be represented by a permutation diagram such that the orderings of the $x$-coordinates on $\ell_{1}$ and $\ell_{2}$ are consistent with $\prec_{1}$ and $\prec_{2}$, respectively, and that ${\mathtt{x}}_2(x)={\mathtt{x}}_1(x)+1$ for $x\in X$ and ${\mathtt{x}}_2(y)={\mathtt{x}}_1(y)-1$ for $y\in Y$.

Since $G$ is connected, the last vertex in $\prec_{1}$ belongs to $Y$, the first vertex in $\prec_{2}$ belongs to $Y$, and the last vertex in $\prec_{2}$ belongs to $X$.

By Lemma \[lem:rightanglerep\], $G$ can be represented by a permutation diagram $D'$ in which ${\mathtt{x}}_{2}(x)={\mathtt{x}}_{1}(x)+1$ for $x \in X$ and ${\mathtt{x}}_{2}(y)={\mathtt{x}}_{1}(y)-1$ for $y \in Y$. Let $\prec'_{1}$ and $\prec'_{2}$ be the permutation orderings corresponding to $\ell_{1}$ and $\ell_{2}$, respectively, in this diagram $D'$. Lemma \[lem:uniquerep\] and the assumption on the first vertex in $\prec_{1}$ imply that $\prec_{1}$ is neighborhood-equivalent to $\prec'_{1}$ or $(\prec'_{2})^{R}$. We may assume that $\prec_{1}$ is neighborhood-equivalent to $\prec'_{1}$ since otherwise we can rotate the diagram $D'$ by $180$ degrees and get a permutation diagram of $G$ in which the ordering on $\ell_{1}$ is $\prec_{1}$, ${\mathtt{x}}_{2}(x)={\mathtt{x}}_{1}(x)+1$ for $x \in X$, and ${\mathtt{x}}_{2}(y)={\mathtt{x}}_{1}(y)-1$ for $y \in Y$.

Now we can construct a desired permutation diagram of $G$ using $\prec_{1}$ and $D'$ by appropriately giving a mapping between segments and vertices. That is, for each $i \in \{1, \dots, |X \cup Y|\}$, we assign the $i$th vertex in $\prec_{1}$ to the segment in $D'$ with the $i$th smallest $x$-coordinate on $\ell_1$. This new diagram is a permutation diagram of $G$ since $\prec_{1}$ is neighborhood-equivalent to $\prec'_{1}$. Since $G$ and $\prec_{1}$ uniquely determine the ordering on $\ell_{2}$, the $x$-coordinates ${\mathtt{x}}_{2}$ on $\ell_{2}$ are consistent with $\prec_{2}$.

Double-threshold graphs as permutation graphs {#sec:permutation}
=============================================

In this section, we show that double-threshold graphs are strongly related to permutation graphs. We first show that all double-threshold graphs are permutation graphs. An illustration of the following lemma is given in [ \[fig:lem3-1\]]{}.

![An illustration of Lemma \[lem:DTGisPerm\]. (Left) A double-threshold graph represented in the form of [ \[fig:dtg\_example1\]]{}. The blue points correspond to the vertices $v$ with ${\mathtt{w}}(v) \leq {\mathtt{lb}}/2$. The red points correspond to the vertices $v$ with ${\mathtt{lb}}/2 < {\mathtt{w}}(v) \leq {\mathtt{ub}}/2$. (Right) The permutation diagram obtained by applying Lemma \[lem:DTGisPerm\]. The vertices are labeled from $1$ to $9$ in the increasing order of the weight ${\mathtt{w}}$. According to the construction in Lemma \[lem:DTGisPerm\], on $\ell_1$, the blue and red points are reflected around ${\mathtt{ub}}/2$. On $\ell_2$, the blue points are reflected around ${\mathtt{lb}}/2$.[]{data-label="fig:lem3-1"}](\figdir/lem3-1)

\[lem:DTGisPerm\] Every double-threshold graph is a permutation graph.

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}}$ with ${\mathtt{lb}}< {\mathtt{ub}}$. By Lemma \[lem:nice-representation\], we can assume for every pair of vertices $u$ and $v$ that ${\mathtt{w}}(u) \ne {\mathtt{w}}(v)$ and ${\mathtt{w}}(u) + {\mathtt{w}}(v) \notin \{{\mathtt{lb}},{\mathtt{ub}}\}$. From ${\mathtt{w}}$, ${\mathtt{lb}}$ and ${\mathtt{ub}}$, we construct a permutation diagram of $G$.

Let $\ell_{1}$ and $\ell_{2}$ be two horizontal parallel lines. For each vertex $v \in V$, we set the $x$-coordinates ${\mathtt{x}}_{1}(v)$ and ${\mathtt{x}}_{2}(v)$ on $\ell_{1}$ and $\ell_{2}$, respectively, as follows: $$\begin{aligned}
  {\mathtt{x}}_{1}(v) &=  \max\{{\mathtt{w}}(v), {\mathtt{ub}}- {\mathtt{w}}(v)\}, \\
  {\mathtt{x}}_{2}(v) &=  \max\{{\mathtt{w}}(v), {\mathtt{lb}}- {\mathtt{w}}(v)\}.\end{aligned}$$ By connecting ${\mathtt{x}}_{1}(v)$ and ${\mathtt{x}}_{2}(v)$ with a line segment for each $v \in V(G)$, we get a permutation diagram. We now show that this diagram represents $G$. Note that the endpoints on the lines $\ell_{1}$ and $\ell_{2}$ are distinct since ${\mathtt{w}}(u) \ne {\mathtt{w}}(v)$ and ${\mathtt{w}}(u) + {\mathtt{w}}(v) \notin \{{\mathtt{lb}},{\mathtt{ub}}\}$ if $u \ne v$.

In the following, let $u$ and $v$ be two vertices such that ${\mathtt{w}}(u) < {\mathtt{w}}(v)$.

${\mathtt{w}}(u) < {\mathtt{w}}(v) < {\mathtt{lb}}/2$. As ${\mathtt{w}}(u) + {\mathtt{w}}(v) < {\mathtt{lb}}$, we have $uv \notin E$. On the other hand, it holds that ${\mathtt{x}}_{1}(u) = {\mathtt{ub}}- {\mathtt{w}}(u) > {\mathtt{ub}}- {\mathtt{w}}(v) = {\mathtt{x}}_{1}(v)$ and ${\mathtt{x}}_{2}(u) = {\mathtt{lb}}- {\mathtt{w}}(u) > {\mathtt{lb}}- {\mathtt{w}}(v) = {\mathtt{x}}_{2}(v)$. This implies that the line segments corresponding to $u$ and $v$ do not cross.

${\mathtt{ub}}/2 < {\mathtt{w}}(u) < {\mathtt{w}}(v)$. Since ${\mathtt{w}}(u) + {\mathtt{w}}(v) > {\mathtt{ub}}$, $uv \notin E$ holds. The line segments of $u$ and $v$ do not cross as ${\mathtt{x}}_{1}(u) = {\mathtt{w}}(u) < {\mathtt{w}}(v) = {\mathtt{x}}_{1}(v)$ and ${\mathtt{x}}_{2}(u) = {\mathtt{w}}(u) < {\mathtt{w}}(v) = {\mathtt{x}}_{2}(v)$.

${\mathtt{lb}}/2 \le {\mathtt{w}}(u) < {\mathtt{w}}(v) \le {\mathtt{ub}}/2$. We have ${\mathtt{lb}}\le {\mathtt{w}}(u) + {\mathtt{w}}(v) \le {\mathtt{ub}}$, and thus $uv \in E$. The line segments of $u$ and $v$ cross as ${\mathtt{x}}_{1}(u) = {\mathtt{ub}}- {\mathtt{w}}(u) > {\mathtt{ub}}- {\mathtt{w}}(v) = {\mathtt{x}}_{1}(v)$ and ${\mathtt{x}}_{2}(u) = {\mathtt{w}}(u) < {\mathtt{w}}(v) = {\mathtt{x}}_{2}(v)$.

${\mathtt{w}}(u) < {\mathtt{lb}}/2$ and ${\mathtt{w}}(v) > {\mathtt{ub}}/2$. We show that $({\mathtt{x}}_{1}(u) - {\mathtt{x}}_{1}(v))({\mathtt{x}}_{2}(u) - {\mathtt{x}}_{2}(v)) < 0$ (that is, the line segments of $u$ and $v$ cross) if and only if ${\mathtt{lb}}< {\mathtt{w}}(u) + {\mathtt{w}}(v) < {\mathtt{ub}}$ as follows: $$\begin{aligned}
  &({\mathtt{x}}_{1}(u) - {\mathtt{x}}_{1}(v))({\mathtt{x}}_{2}(u) - {\mathtt{x}}_{2}(v)) < 0 \\
  {}\iff{}&
  (({\mathtt{ub}}- {\mathtt{w}}(u)) - {\mathtt{w}}(v)) (({\mathtt{lb}}-{\mathtt{w}}(u)) - {\mathtt{w}}(v)) < 0 \\
  {}\iff{}&
  ({\mathtt{ub}}- {\mathtt{w}}(u) - {\mathtt{w}}(v) < 0 \text{ and } {\mathtt{lb}}- {\mathtt{w}}(u) - {\mathtt{w}}(v) > 0)
  \text{ or } \\
  & ({\mathtt{ub}}- {\mathtt{w}}(u) - {\mathtt{w}}(v) > 0 \text{ and } {\mathtt{lb}}- {\mathtt{w}}(u) - {\mathtt{w}}(v) < 0) \\
  {}\iff{}&
  ({\mathtt{ub}}< {\mathtt{w}}(u) + {\mathtt{w}}(v) < {\mathtt{lb}}) \text{ or }
  ({\mathtt{lb}}< {\mathtt{w}}(u) + {\mathtt{w}}(v) < {\mathtt{ub}}) \\
  {}\iff{}&
  {\mathtt{lb}}< {\mathtt{w}}(u) + {\mathtt{w}}(v) < {\mathtt{ub}}.\end{aligned}$$

${\mathtt{w}}(u) < {\mathtt{lb}}/2$ and ${\mathtt{lb}}/2 \le {\mathtt{w}}(v) \le {\mathtt{ub}}/2$. $$\begin{aligned}
  &({\mathtt{x}}_{1}(u) - {\mathtt{x}}_{1}(v))({\mathtt{x}}_{2}(u) - {\mathtt{x}}_{2}(v)) < 0 \\
  {}\iff{}&
  (({\mathtt{ub}}-{\mathtt{w}}(u)) - ({\mathtt{ub}}-{\mathtt{w}}(v))) (({\mathtt{lb}}-{\mathtt{w}}(u)) - {\mathtt{w}}(v))  < 0 \\
  {}\iff{}&
   (-{\mathtt{w}}(u)+{\mathtt{w}}(v)) ({\mathtt{lb}}-{\mathtt{w}}(u) - {\mathtt{w}}(v)) < 0 \\
  {}\iff{}&
  {\mathtt{lb}}< {\mathtt{w}}(u) + {\mathtt{w}}(v) \qquad \qquad\ \ (\because {\mathtt{w}}(u) < {\mathtt{w}}(v))\\
  {}\iff{}&
  {\mathtt{lb}}< {\mathtt{w}}(u)+{\mathtt{w}}(v) < {\mathtt{ub}}.
  \qquad (\because {\mathtt{w}}(u) + {\mathtt{w}}(v) < {\mathtt{lb}}/2 + {\mathtt{ub}}/2 < {\mathtt{ub}})\end{aligned}$$

${\mathtt{lb}}/2 \le {\mathtt{w}}(u) \le {\mathtt{ub}}/2$ and ${\mathtt{w}}(v) > {\mathtt{ub}}/2$. $$\begin{aligned}
  &({\mathtt{x}}_{1}(u) - {\mathtt{x}}_{1}(v))({\mathtt{x}}_{2}(u) - {\mathtt{x}}_{2}(v)) < 0
  \\ {}\iff{}&
  (({\mathtt{ub}}-{\mathtt{w}}(u)) - {\mathtt{w}}(v)) ({\mathtt{w}}(u) - {\mathtt{w}}(v))  < 0
  \\ {}\iff{}&
  {\mathtt{w}}(u)+{\mathtt{w}}(v) < {\mathtt{ub}}\qquad  \qquad\ \ (\because {\mathtt{w}}(u) < {\mathtt{w}}(v))
  \\ {}\iff{}&
  {\mathtt{lb}}< {\mathtt{w}}(u)+{\mathtt{w}}(v) < {\mathtt{ub}}.
  \qquad (\because {\mathtt{w}}(u) + {\mathtt{w}}(v) > {\mathtt{lb}}/2 + {\mathtt{ub}}/2 > {\mathtt{lb}}) \end{aligned}$$

Therefore, the permutation diagram represents $G$, and thus the lemma follows.

Note that the converse of Lemma \[lem:DTGisPerm\] does not hold in general. For example, the disjoint union of two triangles is a permutation graph but not a double-threshold graph by Lemma \[lem:at-most-one-nonbipartite\]. We next show that the converse holds for bipartite graphs. An illustration of the following lemma is given in [ \[fig:lem3-2\]]{}.

![An illustration of Lemma \[lem:biperm-&gt;dtg\]. (Left) A permutation diagram of a bipartite permutation graph $G=(X,Y;E)$ represented in the form of Lemma \[lem:rightanglerep\]. In this example, $X=\{1,2,3,4\}$ and $Y=\{a,b,c,d\}$. (Right) The graph $G$ is represented as a double-threshold graph. The graph is shown in the form of [ \[fig:dtg\_example1\]]{}. The construction is based on the proof of Lemma \[lem:biperm-&gt;dtg\]. []{data-label="fig:lem3-2"}](\figdir/lem3-2){width="\textwidth"}

\[lem:biperm-&gt;dtg\] Every bipartite permutation graph is a double-threshold graph.

Let $G = (X,Y;E)$ be a bipartite permutation graph. By Lemma \[lem:rightanglerep\], $G$ can be represented by a permutation diagram in which ${\mathtt{x}}_{2}(x) = {\mathtt{x}}_{1}(x) + 1$ for $x \in X$ and ${\mathtt{x}}_{2}(y) = {\mathtt{x}}_{1}(y) - 1$ for $y \in Y$. Thus, for $x \in X$ and $y \in Y$, $xy \in E$ if and only if $0 \le {\mathtt{x}}_{1}(y) - {\mathtt{x}}_{1}(x) \le 2$. Without loss of generality, we assume that ${\mathtt{x}}_{1}(z) > 1$ for every $z \in X \cup Y$.

We set ${\mathtt{lb}}= 0$ and ${\mathtt{ub}}= 2$. We set ${\mathtt{w}}(x) = -{\mathtt{x}}_{1}(x)$ for each $x \in X$, and ${\mathtt{w}}(y) = {\mathtt{x}}_{1}(y)$ for each $y \in Y$. Now for $x \in X$ and $y \in Y$, $$0 \le {\mathtt{w}}(y) + {\mathtt{w}}(x) \le 2
  \iff
  0 \le {\mathtt{x}}_{1}(y) - {\mathtt{x}}_{1}(x) \le 2.$$ By the assumption that ${\mathtt{x}}_{1}(z) > 1$ for every $z \in X \cup Y$, we have ${\mathtt{w}}(x) + {\mathtt{w}}(x') < -2$ for all $x,x' \in X$ and ${\mathtt{w}}(y) + {\mathtt{w}}(y') > 2$ for all $y,y' \in Y$. Therefore, $G$ is a double-threshold graph defined by ${\mathtt{w}}$, ${\mathtt{lb}}= 0$, and ${\mathtt{ub}}= 2$.

\[cor:bipartite\] The bipartite double-threshold graphs are exactly the bipartite permutation graphs.

By definition, a bipartite permutation graph is bipartite. Thus, the class of bipartite permutation graphs is contained in the class of bipartite graphs. By Lemma \[lem:biperm-&gt;dtg\], the class of bipartite permutation graphs is contained in the class of double-threshold graphs. Hence, the class of bipartite permutation graphs is contained in the class of bipartite double-threshold graphs.

On the other hand, by Lemma \[lem:DTGisPerm\], every double-threshold graph is a permutation graph. Thus, the class of bipartite double-threshold graphs is contained in the class of bipartite permutation graphs.

New characterization {#sec:characterization}
====================

Let $G=(V,E)$ be a graph. From $G$ and a vertex subset $M \subseteq V$, we construct an auxiliary bipartite graph $G'_{M}=(V',E')$ defined as follows: $$\begin{aligned}
    V' &= \{v,\overline{v} \mid v \in V\},\\
    E' &= \{u\overline{v} \mid uv \in E\} \cup \{v\overline{v} \mid v \in M\}.\end{aligned}$$ An example is given in [ \[fig:auxgraph\_example1\]]{}.

![An example of an auxiliary bipartite graph. (Left) A graph $G$, and $M=\{e,f\}$. (Right) The auxiliary bipartite graph $G'_M$. []{data-label="fig:auxgraph_example1"}](\figdir/auxgraph_example1)

\[lem:GMconn\] For a connected non-bipartite graph $G=(V, E)$ and a vertex subset $M \subseteq V$, $G'_{M}$ is connected.

For any $u, v \in V$, since $G$ is connected and non-bipartite, $G$ contains both an odd walk and an even walk from $u$ to $v$. This shows that $G'_{M}$ contains walks from $u$ to $v$, from $u$ to $\bar v$, from $\bar u$ to $v$, and from $\bar u$ to $\bar v$. Hence, $G'_{M}$ is connected.

For the auxiliary graph $G'_{M} = (V', E')$ of $G=(V,E)$, a linear ordering on $V'$ represented by $\langle w_1, w_2, \dots, w_{2n} \rangle$ is *symmetric* if $w_i=v$ implies $w_{2n-i+1}=\bar v$ for any $v \in V$ and any $i \in \{1,2,\dots, 2n\}$.

The next is the key lemma for our characterization.

\[lem:key-lemma\] Let $G=(V,E)$ be a non-bipartite graph and $M \subseteq V$. The following are equivalent.

1.  $G$ is a double-threshold graph defined by ${\mathtt{w}}\colon V \to {\mathbb{R}}$ and ${\mathtt{lb}},{\mathtt{ub}}\in {\mathbb{R}}$ such that $M = \{v \in V \mid {\mathtt{lb}}/2 \le {\mathtt{w}}(v) \le {\mathtt{ub}}/2\}$. \[itm:dtg\_with\_M\]

2.  the auxiliary graph $G'_{M} = (V',E')$ can be represented by a permutation diagram in which both $\prec_1$ and $\prec_2$ are symmetric.\[itm:sym\_diagram\]

(\[itm:dtg\_with\_M\] $\implies$ \[itm:sym\_diagram\]) An illustration is given in [ \[fig:lem4-2\]]{}. Let $G$ be a double-threshold graph defined by ${\mathtt{w}}\colon V \to {\mathbb{R}}$ and ${\mathtt{lb}}, {\mathtt{ub}}\in {\mathbb{R}}$ such that $M = \{v \in V \mid {\mathtt{lb}}/2 \le {\mathtt{w}}(v) \le {\mathtt{ub}}/2\}$. By Lemma \[lem:nice-representation\], we can assume that ${\mathtt{lb}}= 0$ and ${\mathtt{ub}}= 2$, that ${\mathtt{w}}(u) + {\mathtt{w}}(v) \notin \{0,2\}$ for every $(u,v) \in V^{2}$, and that ${\mathtt{w}}(u) \ne {\mathtt{w}}(v)$ if $u \ne v$. We construct a permutation diagram of $G'_{M}$ as follows. Let $\ell_{1}$ and $\ell_{2}$ be two horizontal parallel lines. For each vertex $w \in V'$, we set the $x$-coordinates ${\mathtt{x}}_{1}(w)$ and ${\mathtt{x}}_{2}(w)$ on $\ell_{1}$ and $\ell_{2}$ as follows: for any $v\in V$, $$\begin{aligned}
    {\mathtt{x}}_1(v)&={\mathtt{w}}(v)-1, & {\mathtt{x}}_1(\bar v)&=1-{\mathtt{w}}(v), \\
    {\mathtt{x}}_2(v)&={\mathtt{w}}(v),   & {\mathtt{x}}_2(\bar v)&=-{\mathtt{w}}(v).\end{aligned}$$ Since ${\mathtt{w}}(u) + {\mathtt{w}}(v) \notin \{0,2\}$ for every $(u,v) \in V^{2}$ and ${\mathtt{w}}(u) \ne {\mathtt{w}}(v)$ if $u \ne v$, the $x$-coordinates are distinct on $\ell_{1}$ and on $\ell_{2}$. By connecting ${\mathtt{x}}_{1}(w)$ and ${\mathtt{x}}_{2}(w)$ with a line segment for each $w \in V'$, we get a permutation diagram. The line segments corresponding to the vertices in $V$ have negative slopes, and the ones corresponding to the vertices in $V' \setminus V$ have positive slopes. Thus, for any two vertices $u,v \in V$, the line segments corresponding to $u$ and $\bar{v}$ cross if and only if both ${\mathtt{x}}_1(u) \le {\mathtt{x}}_1(\bar v)$ and ${\mathtt{x}}_2(u) \ge {\mathtt{x}}_2(\bar v)$ hold, which is equivalent to $0 \le {\mathtt{w}}(u)+{\mathtt{w}}(v) \le 2$, and thus to $u \bar{v} \in E'$. Similarly, the line segments corresponding to $v$ and $\bar{v}$ cross if and only if $0 \le 2 {\mathtt{w}}(v) \le 2$, i.e., $v \in M$. This shows that the obtained permutation diagram represents $G'_{M}$. Let $\prec_{1}$ be the ordering on $V'$ defined by ${\mathtt{x}}_{1}$. Since ${\mathtt{x}}_{1}(v) = - {\mathtt{x}}_{1}(\bar{v})$ for each $v \in V$, if $v$ is the $i$th vertex in $\prec_{1}$, then $\bar{v}$ is the $i$th vertex in $\prec_{1}^{R}$. This implies that $\bar{v}$ is the $(2n-i+1)$st vertex in $\prec_{1}$, and thus $\prec_{1}$ is symmetric. In the same way, we can show that the ordering $\prec_{2}$ defined by ${\mathtt{x}}_{2}$ is symmetric.

![An illustration of (\[itm:dtg\_with\_M\] $\implies$ \[itm:sym\_diagram\]) in Lemma \[lem:key-lemma\]. (Top left) A double-threshold graph $G$ with $M=\{4,5\}$. The auxiliary bipartite graph $G'_M$ is also depicted. (Top right) A representation of $G$ in the form of [ \[fig:dtg\_example1\]]{}. (Bottom) A permutation diagram of $G'_M$ as given in the proof. []{data-label="fig:lem4-2"}](\figdir/lem4-2)

(\[itm:sym\_diagram\] $\implies$ \[itm:dtg\_with\_M\]) Suppose we are given a permutation diagram of $G'_{M}$ in which both $\prec_1$ and $\prec_2$ are symmetric. We may assume by symmetry that the first vertex in $\prec_{1}$ belongs to $V$. Since $G'_{M}$ is connected by Lemma \[lem:GMconn\], Corollary \[cor:rightanglerep\] shows that we can represent $G'_{M}$ by a permutation diagram in which the $x$-coordinates ${\mathtt{x}}_{1}$ and ${\mathtt{x}}_{2}$ on $\ell_{1}$ and $\ell_{2}$ satisfy that $${\mathtt{x}}_2(v)={\mathtt{x}}_1(v)+1 \quad \mbox{and} \quad {\mathtt{x}}_2(\bar v)={\mathtt{x}}_1(\bar v)-1  \quad (v\in V) \label{eq:x1x2}$$ and that the orderings of the $x$-coordinates on $\ell_{1}$ and $\ell_{2}$ are consistent with $\prec_{1}$ and $\prec_{2}$, respectively. Since $\prec_{1}$ is symmetric, if $u, v \in V$ are the $i$th and the $j$th vertices in $\prec_{1}$, then $\bar{u}, \bar{v}$ are the $(2n-i+1)$st and the $(2n-j+1)$st vertices in $\prec_{1}$. Since $i < 2n-j+1$ is equivalent to $j < 2n-i+1$, we have that $u \prec_{1} \bar{v}$ if and only if $v \prec_{1} \bar{u}$. As ${\mathtt{x}}_{1}$ is consistent with $\prec_{1}$, it holds for $u, v \in V$ that ${\mathtt{x}}_1(u) \le {\mathtt{x}}_1(\bar v)$ if and only if ${\mathtt{x}}_1(v) \le {\mathtt{x}}_1(\bar u)$, and hence $${\mathtt{x}}_1(u) \le {\mathtt{x}}_1(\bar v)
  \iff 
  {\mathtt{x}}_1(u)+{\mathtt{x}}_1(v) \le {\mathtt{x}}_1(\bar v)+{\mathtt{x}}_1(\bar u).$$ Similarly, we can show that for $u,v \in V$, $${\mathtt{x}}_2(u) \ge {\mathtt{x}}_2(\bar v)
  \iff
  {\mathtt{x}}_2(u)+{\mathtt{x}}_2(v) \ge {\mathtt{x}}_2(\bar v)+{\mathtt{x}}_2(\bar u).$$ Thus, for any two distinct vertices $u,v \in V$, it holds that $$\begin{aligned}
  uv \in E
    & \iff u\bar v \in E' \notag \\
    & \iff {\mathtt{x}}_1(u) \le {\mathtt{x}}_1(\bar v) \mbox{ and } {\mathtt{x}}_2(u) \ge {\mathtt{x}}_2(\bar v) \notag \\
    & \iff {\mathtt{x}}_1(u)+{\mathtt{x}}_1(v) \le {\mathtt{x}}_1(\bar v) + {\mathtt{x}}_1(\bar u) \mbox{ and } {\mathtt{x}}_2(u)+{\mathtt{x}}_2(v) \ge {\mathtt{x}}_2(\bar v)+{\mathtt{x}}_2(\bar u). \label{eq:weight01} 
$$ For each $v\in V$, define $${\mathtt{w}}(v)= \frac{{\mathtt{x}}_2(v)-{\mathtt{x}}_2(\bar v)}{2}.$$ By (\[eq:x1x2\]), we can see that (\[eq:weight01\]) is equivalent to $$0 \le {\mathtt{w}}(u)+{\mathtt{w}}(v) \le 2,$$ which shows that ${\mathtt{w}}$, ${\mathtt{lb}}=0$, and ${\mathtt{ub}}= 2$ define $G$. Furthermore, for any $v\in V$, $$\begin{aligned}
    v \in M &\iff v \bar v \in E' \\
            & \iff {\mathtt{x}}_1(v) \le {\mathtt{x}}_1(\bar v) \mbox{ and } {\mathtt{x}}_2(v) \ge {\mathtt{x}}_2(\bar v) \\
            & \iff 0 \le {\mathtt{w}}(v) \le 1, \end{aligned}$$ which shows that $M = \{v \in V \mid 0\le {\mathtt{w}}(v) \le 1\}$.

To utilize Lemma \[lem:key-lemma\], we need to find the set $M$ of mid-weight vertices; that is, the vertices with weights in the range $[{\mathtt{lb}}/2, {\mathtt{ub}}/2]$. The first observation is that $M$ has to be a clique as the weight sum of any two vertices in $M$ is in the range $[{\mathtt{lb}}, {\mathtt{ub}}]$. In the following, we show that a special kind of maximum cliques can be chosen as $M$. To this end, we first prove that we only need to consider (inclusion-wise) maximal cliques.

\[lem:mid-weight\_maximal-clique\] For a non-bipartite double-threshold graph $G = (V,E)$, there exist ${\mathtt{w}}\colon V \to {\mathbb{R}}$ and ${\mathtt{lb}}, {\mathtt{ub}}\in {\mathbb{R}}$ defining $G$ such that $\{v \in V \mid {\mathtt{lb}}/2 \le {\mathtt{w}}(v) \le {\mathtt{ub}}/2\}$ is a maximal clique of $G$.

Let $G$ be a non-bipartite double-threshold graph $G = (V,E)$ defined by ${\mathtt{w}}\colon V \to {\mathbb{R}}$ and ${\mathtt{lb}}, {\mathtt{ub}}\in {\mathbb{R}}$. Let $M = \{v \in V \mid {\mathtt{lb}}/2 \le {\mathtt{w}}(v) \le {\mathtt{ub}}/2\}$. We choose ${\mathtt{w}}$, ${\mathtt{lb}}$, and ${\mathtt{ub}}$ in such a way that for any ${\mathtt{w}}'\colon V \to {\mathbb{R}}$ and ${\mathtt{lb}}', {\mathtt{ub}}' \in {\mathbb{R}}$ defining $G$, $M$ is not a proper subset of $\{v \in V \mid {\mathtt{lb}}'/2 \le {\mathtt{w}}'(v) \le {\mathtt{ub}}'/2\}$. Suppose to the contrary that $M$ is not a maximal clique of $G$. Observe that if $M = \emptyset$, then $V$ can be partitioned into two independent sets $\{v \in V \mid {\mathtt{w}}(v) < {\mathtt{lb}}/2\}$ and $\{v \in V \mid {\mathtt{w}}(v) > {\mathtt{ub}}/2\}$, which is a contradiction to the non-bipartiteness of $G$. Hence, $M$ is non-empty.

Let $G'_{M}$ be the auxiliary graph constructed from $G$ and $M$ as before. By Lemma \[lem:key-lemma\], $G'_{M}$ has a permutation diagram in which both ${\prec_{1}} = \langle w_{1}, \dots, w_{2n} \rangle$ and ${\prec_{2}} = \langle w'_{1}, \dots, w'_{2n} \rangle$ are symmetric. Let $\overline{M} = \{\bar{v} \mid v \in M\}$. By the definition of $G'_{M}$, $M \cup \overline{M}$ induces a complete bipartite graph in $G'_{M}$. By symmetry, we may assume that $M \prec_{1} \overline{M}$ and $\overline{M} \prec_{2} M$. That is, in $\prec_{1}$ all vertices in $M$ appear before any vertex in $\overline{M}$ appears, and in $\prec_{2}$ all vertices in $\overline{M}$ appear before any vertex in $M$ appears. Note that these assumptions imply that for each edge $x \bar{y} \in E(G'_{M})$, $x \prec_{1} \bar{y}$ and $\bar{y} \prec_{2} x$ hold.

As $M$ is not a maximal clique in $G$, there is a vertex $v \notin M$ such that $M \subseteq N_{G}(v)$. If $\bar{v} \prec_{1} v$, then we have $$\begin{aligned}
  M \prec_{1} \bar{v} \prec_{1} v \prec_{1} \overline{M} \quad \text{ and } \quad
  \bar{v} \prec_{2} \overline{M} \prec_{2} M \prec_{2} v \label{eq:maximal_the-1st-case}\end{aligned}$$ since $v \bar{v} \notin E(G'_{M})$, $\overline{M} \subseteq N_{G'_{M}}(v)$, and $M \subseteq N_{G'_{M}}(\bar{v})$. Similarly, if $v \prec_{1} \bar{v}$, then we have $$\begin{aligned}
  v \prec_1 M \prec_{1} \overline{M} \prec_{1} \bar{v} \quad \text{ and } \quad
  \overline{M} \prec_{2} v \prec_{2} \bar{v} \prec_{2} M,\end{aligned}$$ or equivalently, $$\begin{aligned}
  M \prec_{2}^{R} \bar{v} \prec_{2}^{R} v \prec_{2}^{R} \overline{M} \quad \text{ and } \quad
  \bar{v} \prec_{1}^{R} \overline{M} \prec_{1}^{R} M \prec_{1}^{R} v.\end{aligned}$$ Thus, by replacing $\prec_{1}$ with $\prec_{2}^{R}$ and $\prec_{2}$ with $\prec_{1}^{R}$ if necessary, we may assume that holds (see [ \[fig:mid-weight\]]{} (Left)). We further assume that $v$ has the smallest position in $\prec_{1}$ under these conditions.

\[clm:center\] $w_{n+1} = v$ (and thus $w_{n} = \bar{v}$).

\[Proof of Claim \[clm:center\]\] By the symmetry of $\langle w_{1}, \dots, w_{2n} \rangle$, it suffices to show that there is no vertex $x \in V$ such that $\bar{v} \prec_{1} x \prec_{1} v$. Suppose that such a vertex $x$ exists. In $G'_{M}$, $x$ is not adjacent to $\bar{v}$. This implies that $xv \notin E$, and hence $x \notin M$. On the other hand, in $G'_{M}$, $x$ is adjacent to all vertices in $\overline{M}$. Thus, we have $M \subseteq N_{G}(x)$. This contradicts that $v$ has the smallest position in $\prec_{1}$ under those conditions.

Now we obtain $\prec'_{1}$ from $\prec_{1}$ by swapping $v$ and $\bar{v}$ (see [ \[fig:mid-weight\]]{} (Right)). By Claim \[clm:center\], this new ordering $\prec'_{1}$ gives (together with $\prec_{2}$) the graph obtained from $G'_{M}$ by adding the edge $v\bar{v}$. Observe that this new graph can be expressed as $G'_{M \cup \{v\}}$. Since $\prec'_{1}$ and $\prec_{2}$ are symmetric, Lemma \[lem:key-lemma\] implies that there are ${\mathtt{w}}'\colon V \to {\mathbb{R}}$ and ${\mathtt{lb}}', {\mathtt{ub}}' \in {\mathbb{R}}$ defining $G$ such that $\{u \in V \mid {\mathtt{lb}}'/2 \le {\mathtt{w}}'(u) \le {\mathtt{ub}}'/2\} = M \cup \{v\}$. This contradicts the choice of ${\mathtt{w}}$, ${\mathtt{lb}}$, and ${\mathtt{ub}}$.

![(Left) Relative positions of $v$, $\bar{v}$, $M$, and $\overline{M}$. (Right) $\prec'_{1}$ is obtained from $\prec_{1}$ by swapping $v$ and $\bar{v}$.[]{data-label="fig:mid-weight"}](\figdir/mid-weight)

An *efficient maximum clique* $K$ of a graph $G$ is a maximum clique (i.e., a clique of the maximum size) that minimizes the degree sum $\sum_{v \in K} \deg_{G}(v)$. An example is illustrated in [ \[fig:effcliq\_example1\]]{}.

![An example of an efficient maximum clique. (Left) A double-threshold graph $G$ represented in the form of [ \[fig:dtg\_example1\]]{}. (Right) The vertices of $G$ is ordered in the increasing order of their weights. The graph $G$ has two maximum cliques $K_1=\{3,5,6,7\}$ and $K_2=\{4,5,6,7\}$. The degree sums are $\sum_{v \in K_1}\deg_G(v) = 5+4+4+4 = 17$, and $\sum_{v \in K_2}\deg_G(v) = 4+4+4+4 = 16$. Therefore, $K_2$ is the only efficient maximum clique of $G$. []{data-label="fig:effcliq_example1"}](\figdir/effcliq_example1)

We now show that every efficient maximum clique can be the set of mid-weight vertices.

\[lem:efficient-max-clique\] Let $G$ be a non-bipartite double-threshold graph. For every efficient maximum clique $K$ of $G$, there exist ${\mathtt{w}}\colon V \to {\mathbb{R}}$ and ${\mathtt{lb}}, {\mathtt{ub}}\in {\mathbb{R}}$ defining $G$ such that $K = \{v \in V \mid {\mathtt{lb}}/2 \le {\mathtt{w}}(v) \le {\mathtt{ub}}/2\}$.

Let $K$ be an efficient maximum clique of $G$. By Lemma \[lem:DTGisPerm\], $G$ is a permutation graph, and thus cannot contain an induced odd cycle of length 5 or more [@Golumbic04]. As $G$ is non-bipartite, $G$ contains $K_{3}$. This implies that $|K| \ge 3$.

By Lemma \[lem:mid-weight\_maximal-clique\], there exist ${\mathtt{w}}\colon V \to {\mathbb{R}}$ and ${\mathtt{lb}}, {\mathtt{ub}}\in {\mathbb{R}}$ defining $G$ such that $M := \{v \in V \mid {\mathtt{lb}}/2 \le {\mathtt{w}}(v) \le {\mathtt{ub}}/2\}$ is a maximal clique of $G$. Assume that ${\mathtt{w}}$, ${\mathtt{lb}}$, and ${\mathtt{ub}}$ are chosen so that the size of the symmetric difference $|M \vartriangle K| = |M \setminus K| + |K \setminus M|$ is minimized. Assume that $K \ne M$ since otherwise we are done. This implies that $K \not\subseteq M$ and $K \not\supseteq M$ as both $K$ and $M$ are maximal cliques. Observe that $G - M$ is bipartite. This implies that $|K \setminus M| \in \{1,2\}$ and that $K \cap M \ne \emptyset$ as $|K| \ge 3$. Since $K$ is a maximum clique, $|M \setminus K| \le |K \setminus M|$ holds.

Let $u \in K \setminus M$. By symmetry, we may assume that ${\mathtt{w}}(u) < {\mathtt{lb}}/2$. Note that no other vertex in $K$ has weight less than ${\mathtt{lb}}/2$ as $K$ is a clique. Let $v \in M$ be a nonneighbor of $u$ that has the minimum weight among such vertices. Such a vertex exists since $M$ is a maximal clique. Note that $v \in M \setminus K$.

We now observe that $v$ has the minimum weight in $M$. If $w \in M$ is a nonneighbor of $u$, then ${\mathtt{w}}(v) \le {\mathtt{w}}(w)$ follows from the definition of $v$. If $w \in M$ is a neighbor of $u$, then ${\mathtt{w}}(v) < {\mathtt{w}}(w)$ holds, since otherwise ${\mathtt{w}}(u) < {\mathtt{lb}}/2 \le {\mathtt{w}}(w) \le {\mathtt{w}}(v)$ and $uw, wv \in E$ imply that $uv \in E$ as ${\mathtt{lb}}\le {\mathtt{w}}(u) + {\mathtt{w}}(w) \le {\mathtt{w}}(u) + {\mathtt{w}}(v) < {\mathtt{w}}(w) + {\mathtt{w}}(v) \le {\mathtt{ub}}$.

Now we show below that $N(v) = N(u)$.

\[clm:neighborhood-in-M\] $N(u) \cap \{x \mid {\mathtt{w}}(x) < {\mathtt{lb}}/2\} = N(v) \cap \{x \mid {\mathtt{w}}(x) < {\mathtt{lb}}/2\}$.

\[Proof of Claim \[clm:neighborhood-in-M\]\] Since ${\mathtt{w}}(u) < {\mathtt{lb}}/2$, $N(u) \cap \{x \mid {\mathtt{w}}(x) < {\mathtt{lb}}/2\} = \emptyset$. Suppose to the contrary that $v$ has a neighbor $x$ with ${\mathtt{w}}(x) < {\mathtt{lb}}/2$. The maximality of $M$ implies that $x$ has a non-neighbor $y \in M$. Since $y \in M$, ${\mathtt{w}}(v) \le {\mathtt{w}}(y)$ holds. This implies that ${\mathtt{w}}(x) \le {\mathtt{w}}(v) \le {\mathtt{w}}(y)$ and $xv, vy \in E$, which contradicts that $xy \notin E$.

\[clm:neighborhood-in-M2\] $N(u) \cap M = N(v) \cap M$.

\[Proof of Claim \[clm:neighborhood-in-M2\]\] Since $M$ is a clique and $v \in M$, we have $N(v) \cap M = M \setminus \{v\}$. Thus, the claim is equivalent to $M \setminus \{v\} \subseteq N(u)$. This holds if $M \setminus K = \{v\}$. Assume that $M \setminus K = \{v, v'\}$ for some $v' \ne v$. To show the claim, it suffices to show that $uv' \in E$.

Since $|M \setminus K| \le |K \setminus M| \le 2$, we have $K \setminus M = \{u,u'\}$ for some $u' \ne u$. Since ${\mathtt{w}}(u) < {\mathtt{lb}}/2$ and $u' \in K \setminus M$, we have ${\mathtt{w}}(u') > {\mathtt{ub}}/2$. Let $w \in M \cap K$. If ${\mathtt{w}}(w) > {\mathtt{w}}(v')$, then we have $u'v, u'v' \in E$ since ${\mathtt{w}}(v) \le {\mathtt{w}}(v') < {\mathtt{w}}(w) \le {\mathtt{w}}(u')$ and $vw, v'w, wu' \in E$. This contradicts the maximality of $M$. Hence, ${\mathtt{w}}(w) \le {\mathtt{w}}(v')$ holds. This implies that $uv' \in E$ as ${\mathtt{w}}(u) \le {\mathtt{w}}(w) \le {\mathtt{w}}(v')$ and $uw, wv' \in E$.

\[clm:neighborhood-in-L\] $N(u) \cap \{x \mid {\mathtt{w}}(x) > {\mathtt{ub}}/2\} \supseteq N(v) \cap \{x \mid {\mathtt{w}}(x) > {\mathtt{ub}}/2\}$.

\[Proof of Claim \[clm:neighborhood-in-L\]\] Let $w \in K \cap M$. For $z \in N(v)$ with ${\mathtt{w}}(z) > {\mathtt{ub}}/2$, we have $z \in N(u)$ as follows: ${\mathtt{lb}}\le {\mathtt{w}}(u) + {\mathtt{w}}(w) \le {\mathtt{w}}(u) + {\mathtt{ub}}/2 < {\mathtt{w}}(u) + {\mathtt{w}}(z) < {\mathtt{lb}}/2 + {\mathtt{w}}(z) < {\mathtt{w}}(v) + {\mathtt{w}}(z) \le {\mathtt{ub}}$.

We are now ready to show that $N(v) = N(u)$. Claims \[clm:neighborhood-in-M\], \[clm:neighborhood-in-M2\], and \[clm:neighborhood-in-L\] imply that $N(v) \subseteq N(u)$. Suppose to the contrary that $N(v) \subsetneq N(u)$. We show that $K$ cannot be an efficient maximum clique in this case. Let $K' = K \setminus \{u\} \cup \{v\}$. We first argue that $K'$ is a (maximum) clique. If $K \setminus M = \{u\}$, then $K' = M$ is a clique. Assume that $K \setminus M = \{u, u'\}$ for some $u' \ne u$. As in the proof of Claim \[clm:neighborhood-in-M2\], ${\mathtt{w}}(u') > {\mathtt{ub}}/2$ holds. Let $w \in K \cap M$. Then, $vw, wu' \in E$. Since ${\mathtt{w}}(v) \le {\mathtt{w}}(w) \le {\mathtt{ub}}/2 < {\mathtt{w}}(u')$, we have $vu' \in E$. Thus, $K'$ is a clique. The assumption $N(v) \subsetneq N(u)$ implies that $\deg_{G}(v) < \deg_{G}(u)$, and thus, $$\sum_{w \in K'} \deg_{G}(w) = \left(\sum_{w \in K} \deg_{G}(w)\right) - \deg_{G}(u) + \deg_{G}(v) < \sum_{w \in K} \deg_{G}(w).$$ This contradicts that $K$ is efficient. Therefore, we conclude that $N(v) = N(u)$.

Now, we define a weight function ${\mathtt{w}}'\colon V \to {\mathbb{R}}$ by setting ${\mathtt{w}}'(u) = {\mathtt{w}}(v)$, ${\mathtt{w}}'(v) = {\mathtt{w}}(u)$, and ${\mathtt{w}}'(x) = {\mathtt{w}}(x)$ for all $x \in V \setminus \{u,v\}$. Then, ${\mathtt{w}}'$, ${\mathtt{lb}}$, and ${\mathtt{ub}}$ define $G$ and $M' := \{w \in V \mid {\mathtt{lb}}/2 \le {\mathtt{w}}'(w) \le {\mathtt{ub}}/2\} = M \cup \{u\} \setminus \{v\}$ as $N(u) = N(v)$. This contradicts the choice of ${\mathtt{w}}$ as $|M' \vartriangle K| < |M \vartriangle K|$.

Next, we show that the symmetry required in Lemma \[lem:key-lemma\] follows for free when $M$ is a clique.

\[lem:perm=sym\] Let $G = (V,E)$ be a connected non-bipartite graph and $M$ be a clique of $G$. Then, $G'_{M}$ is a permutation graph if and only if $G'_{M}$ can be represented by a permutation diagram in which both $\prec_1$ and $\prec_2$ are symmetric.

The if part is trivial. To prove the only-if part, we assume that $G'_{M}$ is a permutation graph.

We first observe that we only need to deal with the *twin-free* case. Assume that $N_{G'_{M}}(u) = N_{G'_{M}}(v)$ (or equivalently $N_{G'_{M}}(\bar{u}) = N_{G'_{M}}(\bar{v})$) for some $u, v \in V$, i.e., $u, v$ are twins in $G'_{M}$. If $G'_{M} - \{v,\bar{v}\}$ has a permutation diagram in which both permutation orderings $\prec_{1}$ and $\prec_{2}$ are symmetric, then we can obtain symmetric permutation orderings $\prec'_{1}$ and $\prec'_{2}$ of $G'_{M}$ by inserting $v$ right after $u$, and $\bar{v}$ right before $\bar{u}$ in both $\prec_{1}$ and $\prec_{2}$. Thus, it suffices to show that $G'_{M} - \{v,\bar{v}\} = (G - v)'_{M \setminus \{v\}}$ has a permutation diagram in which both permutation orderings $\prec_{1}$ and $\prec_{2}$ are symmetric.

Observe that $G-v$ is not necessarily non-bipartite, but $(G - v)'_{M \setminus \{v\}}$ is still connected. Hence, we can assume in the following that no pair of vertices in $G'_{M}$ have the same neighborhood and that $G'_{M}$ is connected (but $G$ is not necessarily non-bipartite). We also assume that $|V| \ge 2$ since otherwise the statement is trivially true.

Let $\prec_{1}$ and $\prec_{2}$ be the permutation orderings corresponding to a permutation diagram of $G'_{M}$. By Lemma \[lem:uniquerep\], the assumption of having no twins implies that $\prec_{1}$, $\prec_{2}$, $\prec_{1}^{\mathrm{R}}$, and $\prec_{2}^{\mathrm{R}}$ are all the permutation orderings of $G'_{M}$. Since $G'_{M}$ is connected, we may assume that the first vertex in $\prec_{1}$ belongs to $V$, the last in $\prec_{1}$ belongs to $V' \setminus V$, the first in $\prec_{2}$ belongs to $V' \setminus V$, and the last vertex in $\prec_{2}$ belongs to $V$. Let $\langle w_{1}, \dots, w_{2n} \rangle$ be the ordering defined by $\prec_{1}$.

Let $\varphi \colon V' \to V'$ be a map such that $\varphi(v) = \bar{v}$ and $\varphi(\bar{v}) = v$ for each $v \in V$. This map $\varphi$ is an automorphism of $G'_{M}$. Thus, $\langle \varphi(w_{1}), \dots, \varphi(w_{2n}) \rangle$ is also a permutation ordering of $G'_{M}$. Let ${\prec'} = \langle \varphi(w_{1}), \dots, \varphi(w_{2n}) \rangle$ denote this ordering. Then, $${\prec'} \in \{\prec_{1}, \prec_{2}, \prec_{1}^{\mathrm{R}}, \prec_{2}^{\mathrm{R}}\}.$$ We claim that ${\prec'} = {\prec_{1}^{\mathrm{R}}}$. First, observe that ${\prec'} \notin \{\prec_{1},\prec_{2}^{\mathrm{R}}\}$ as the first vertex of $\prec'$ belongs to $V' \setminus V$ but the first vertices of $\prec_{1}$ and $\prec_{2}^{\mathrm{R}}$ belong to $V$.

Suppose to the contrary that ${\prec'} = {\prec_{2}}$. Then, for each $w \in V'$, the positions of $w$ in $\prec_{1}$ and $\varphi(w)$ in ${\prec_{2}}$ ($= {\prec'}$) are the same. Thus, $w_{i} \prec_{1} \varphi(w_{i})$ implies $\varphi(w_{i}) \prec_{2} \varphi(\varphi(w_{i})) = w_{i}$. Hence, we have $v \bar{v} \in E(G'_{M})$ for all $v \in V$, and thus $M = V$. As $M$ is a clique, $M = V$ implies that $G$ is a complete graph $K_{|V|}$ and that $G'_{M}$ is a complete bipartite graph $K_{|V|, |V|}$. This contradicts the assumption that $G'_{M}$ has no twins as $|V| \ge 2$. Therefore, we conclude that ${\prec'} = {\prec_{1}^{\mathrm{R}}}$, and in particular that $\varphi(w_{i}) = w_{2n-i+1}$ for each $i$. This means that $w_{i} = v$ implies $w_{2n-i+1} = \bar{v}$ for all $v \in V$ and $i \in \{1,\dots,2n\}$. Hence, $\prec_{1}$ is symmetric.

By putting the facts above together, we obtain the following characterization of non-bipartite double-threshold graphs.

\[thm:non-bipartite\] For a non-bipartite graph $G$, the following are equivalent.

1.  $G$ is a double-threshold graph. \[itm:chara\_dtg\]

2.  For every efficient maximum clique $M$ of $G$, the graph $G'_{M}$ is a permutation graph. \[itm:every\_emc\]

3.  For some efficient maximum clique $M$ of $G$, the graph $G'_{M}$ is a permutation graph. \[itm:some\_emc\]

The implication from \[itm:every\_emc\] to \[itm:some\_emc\] is trivial. To show that \[itm:chara\_dtg\] implies \[itm:every\_emc\], assume that $G$ is a non-bipartite double-threshold graph. Let $M$ be an efficient maximum clique of $G$. By Lemma \[lem:efficient-max-clique\], there exist ${\mathtt{w}}\colon V \to {\mathbb{R}}$ and ${\mathtt{lb}}, {\mathtt{ub}}\in {\mathbb{R}}$ defining $G$ such that $M = \{v \in V \mid {\mathtt{lb}}/2 \le {\mathtt{w}}(v) \le {\mathtt{ub}}/2\}$. Now by Lemma \[lem:key-lemma\], $G'_{M}$ is a permutation graph.

We now show that \[itm:some\_emc\] implies \[itm:chara\_dtg\]. Assume that for an efficient maximum clique $M$ of a non-bipartite graph $G$, the graph $G'_{M}$ is a permutation graph.

Let $H$ be a non-bipartite component of $G$. Then, $H$ contains an induced odd cycle of length $k \ge 3$. This means that, if $H$ does not include $M$, then $G'_{M}$ contains an induced cycle of length $2k \ge 6$. However, this is a contradiction as a permutation graph cannot contain an induced cycle of length at least $5$. Thus, $H$ includes $M$. Also, there is no other non-bipartite component in $G$ as it does not intersect $M$. Since $H$ includes $M$, $H'_{M}$ is a component of $G'_{M}$. By Lemma \[lem:perm=sym\], $H'_{M}$ can be represented by a permutation diagram in which both $\prec_1$ and $\prec_2$ are symmetric, and thus $H$ is a double-threshold graph by Lemma \[lem:key-lemma\].

Let $B$ be a bipartite component of $G$ (if one exists). Since $B$ does not intersect $M$, $G'_{M}$ contains two isomorphic copies of $H$ as components. Since $G'_{M}$ is a permutation graph, $B$ is a permutation graph too. By Corollary \[cor:bipartite\], $B$ is a double-threshold graph.

The discussion so far implies that all components of $G$ are double-threshold graphs and exactly one of them is non-bipartite. By Corollary \[cor:component\], $G$ is a double-threshold graph.

Linear-time recognition algorithm {#sec:algorithm}
=================================

We are now ready to present a linear-time recognition algorithm for double-threshold graphs. Algorithm \[alg:outline\] shows the outline of our algorithm. The main result of this paper (Theorem \[thm:linear-recognition\]) follows from Lemmas \[lem:alg-correctness\] and \[lem:alg-runtime\] below.

\[thm:linear-recognition\] There exists a linear-time algorithm that takes a graph as its input and outputs <span style="font-variant:small-caps;">yes</span> if the graph is a double-threshold graph; outputs <span style="font-variant:small-caps;">no</span> otherwise.

The algorithm for Theorem \[thm:linear-recognition\] is given in Algorithm \[alg:outline\]. The proof of Theorem \[thm:linear-recognition\] boils down to the following two lemmas.

<span style="font-variant:small-caps;">yes</span> Find an efficient maximum clique $M$ of $G$ using $\prec$. <span style="font-variant:small-caps;">yes</span> <span style="font-variant:small-caps;">no</span>

\[lem:alg-correctness\] Algorithm \[alg:outline\] returns <span style="font-variant:small-caps;">yes</span> if and only if the input graph $G$ is a double-threshold graph.

Algorithm \[alg:outline\] returns <span style="font-variant:small-caps;">yes</span> if and only if $G$ is a bipartite permutation graph, or $G$ is a non-bipartite permutation graph and $G'_{M}$ is a permutation graph, where $M$ is an efficient maximum clique of $G$. The correctness follows from Corollary \[cor:bipartite\] and Theorem \[thm:non-bipartite\].

\[lem:alg-runtime\] There exists a linear-time implementation of Algorithm \[alg:outline\].

At Steps 1 and 4, deciding whether a graph is a permutation graph and, if so, computing a permutation ordering can be done in linear time [@McConnellS99]. (When we do this for bipartite graphs, we can use simpler algorithms [@SpinradBS87; @Sprague95].) At Step 2, bipartiteness can be checked in linear time by, e.g., depth-first search. Observe that $|V(G'_{M})| = 2 |V|$ and $|E(G'_{M})| = 2 |E| + |M|$. Thus, it suffices to show that an efficient maximum clique of a permutation graph can be computed in linear time at Step 3.

To find an efficient maximum clique of $G$, we set to each vertex $v \in V$ the weight ${\mathtt{w}}(v) = n^{2} - \deg_{G}(v)$, where $n = |V|$, and then find a maximum-weight clique $M$ of $G$ with respect to these weights. Using the permutation ordering of $G$ computed before, we can find $M$ in linear time [@Golumbic04 pp. 133–134]. We show that $M$ is an efficient maximum clique of $G$. Let $K$ be an efficient maximum clique of $G$. Since ${\mathtt{w}}(K) \le {\mathtt{w}}(M)$, we have $$|K| \cdot n^{2} - \sum_{v \in K} \deg_{G}(v) \le |M| \cdot n^{2} - \sum_{v \in M} \deg_{G}(v). \label{eq:efficient-max-clique}$$ Since $0 \le \sum_{v \in S} \deg_{G}(v) < n^{2}$ for any $S \subseteq V$, it holds that $  |K| \cdot n^{2} - n^{2} < |M| \cdot n^{2}$. Since $|M| \le |K|$, this implies that $|K| = |M|$. By , it holds that $\sum_{v \in K} \deg_{G}(v) \ge \sum_{v \in M} \deg_{G}(v)$. Therefore, $M$ is an efficient maximum clique.

Minimal forbidden induced subgraphs {#sec:forbidden-induced-subgraphs}
===================================

Observe that the class of double-threshold graphs is hereditary. That is, the class is closed under vertex deletions. Such a class can be characterized by the (possibly infinite) list of minimal forbidden induced subgraphs. This section is devoted to the first steps in this direction.

We first show that the graphs in [ \[fig:graph5\]]{} are the non-double-threshold graphs of order at most 5. This small list can be useful for comparing the class with others. For example, one can check that bull, butterfly, and gem are permutation graphs of co-threshold dimension 2.

![The graphs of order at most 5 that are not double-threshold graphs.[]{data-label="fig:graph5"}](\figdir/graphs5)

\[lem:mfis\_with\_order5\] The graphs $C_{5}$, bull, butterfly, and gem are the graphs of order at most 5 that are not double-threshold graphs.

We first show that all four graphs in [ \[fig:graph5\]]{} are not double-threshold graphs. By Lemma \[lem:DTGisPerm\], $C_{5}$ is not a double-threshold graph. Using our new characterization (Theorem \[thm:non-bipartite\]), we can show that bull, butterfly, and gem are non-double-threshold graphs because their auxiliary graphs contain a bipartite net or a bipartite tent as an induced subgraph and thus are not permutation graphs [@HellH04]. See [ \[fig:graph5\_no\]]{}.

![The graphs bull, butterfly, and gem are non-double-threshold graphs as $\text{bull}'_{M}[a,b,c,d,\bar{a},\bar{b},\bar{c}] \simeq \text{bipartite net}$ and $\text{butterfly}'_{M}[a,b,c,d,\bar{a},\bar{b},\bar{c}] = \text{gem}'_{M}[a,b,c,d,\bar{a},\bar{b},\bar{c}] \simeq \text{bipartite tent}$, where $M$ in each graph is the efficient maximum clique formed by the square vertices.[]{data-label="fig:graph5_no"}](\figdir/graphs5_n)

Suppose to the contrary that there is a graph $G$ of order at most 5 that is not a double-threshold graph and not isomorphic to $C_{5}$, bull, butterfly, or gem.

\[clm:mfis\_with\_order5\] $G$ is a connected graph of order exactly 5 that contains $K_{3}$ and at least one of $2K_{2}$, $C_{4}$, and $P_{4}$ as induced subgraphs.

\[Proof of Claim \[clm:mfis\_with\_order5\]\] It is known that the threshold graphs are the $\{2K_{2}, C_{4}, P_{4}\}$-free graphs [@ChvatalH73] and that all bipartite graphs of order at most 5 are permutation graphs [@HellH04]. Thus, by Corollary \[cor:bipartite\], $G$ is a non-bipartite graph of order exactly 5 that contains at least one of $2K_{2}$, $C_{4}$, and $P_{4}$ as an induced subgraph. Since $G$ is non-bipartite and non-isomorphic to $C_{5}$, $G$ has $K_{3}$ as an induced subgraph. If $G$ is not connected, then each component is of order at most 4 and at most one component is non-bipartite. Thus, $G$ is connected by Corollary \[cor:component\].

First assume that $G$ has $K_{3}$ and $2K_{2}$ as induced subgraphs. Fix an induced subgraph of $G$ isomorphic to $2K_{2}$, and let $v$ be the vertex not contained in this $2K_{2}$. The vertex $v$ has degree 3 since $G$ contains $K_{3}$, $G$ is connected, and $G$ is not isomorphic to butterfly. This graph $\overline{\text{P}}$ is a double-threshold graph as shown in [ \[fig:graph5\_y\]]{}.

Next assume that $G$ has $K_{3}$ and $P_{4}$ as induced subgraphs. Fix an induced subgraph of $G$ isomorphic to $P_{4}$, and let $v$ be the vertex not contained in this $P_{4}$. We know that $v$ has degree at most 3 since $G$ is not isomorphic to gem. Also, $v$ cannot be adjacent only to the two inner vertices as $G$ is not isomorphic to bull. Thus, $v$ is adjacent either to the first (or equivalently the last) two vertices or arbitrary three vertices in $P_{4}$. All these cases result in double-threshold graphs $\overline{\text{P}}$, co-fork, and house in [ \[fig:graph5\_y\]]{}.

Finally assume that $G$ has $K_{3}$ and $C_{4}$ as induced subgraphs. Fix an induced subgraph of $G$ isomorphic to $C_{4}$, and let $v$ be the vertex not contained in this $C_{4}$. To have $K_{3}$, $v$ has to be adjacent to two consecutive vertices in $C_{4}$. Thus, $G$ is either house, $\overline{P_{2} \cup P_{3}}$, or $W_{4}$. All these graphs are double-threshold graphs as shown in [ \[fig:graph5\_y\]]{}.

![The double-threshold graphs of order 5 that contain $K_{3}$ and at least one of $2K_{2}$, $C_{4}$, and $P_{4}$. The numbers in the brackets are the lower and upper bounds for each graph.[]{data-label="fig:graph5_y"}](\figdir/graphs5_y)

By Lemma \[lem:at-most-one-nonbipartite\], the disjoint union of two triangles, denoted $2K_{3}$, is not a double-threshold graph. Below we show that this graph is the unique disconnected graph that is a minimal forbidden induced subgraph of double-threshold graphs.

The graph $2K_{3}$ is the unique disconnected minimal forbidden induced subgraph of double-threshold graphs.

First observe that all proper induced subgraphs of $2K_{3}$ are double-threshold graphs, and thus it is a minimal forbidden induced subgraph of double-threshold graphs.

Let $G$ be a disconnected graph that is not a double-threshold graph. Assume that all connected components of $G$ are double-threshold graphs since otherwise $G$ is not minimal. If a component of $G$ is bipartite, then $G$ is not minimal by Lemma \[lem:disjoint-bicomponent\]. Thus, each component of $G$ is non-bipartite. Since a double-threshold graph cannot contain any induced odd cycle of length more than 3, each component of $G$ contains a triangle $K_{3}$. Since $G$ has at least two components, $G$ contains $2K_{3}$ as an induced subgraph.

[^1]: Strictly speaking, the names are not exactly the same. One is written with a hyphen, but the other is written without a hyphen.

[^2]: The symbols $K_{n}$ and $C_{n}$ denote the complete graph and the cycle of $n$ vertices, respectively. For a graph $G$ and an positive integer $k$, $kG$ is the disjoint union of $k$ copies of $G$. The graph *bull* is shown in [ \[fig:graph5\]]{}.
