# Linear-semiorders and their incomparability graphs

Asahi Takaoka  College of Information and Systems, Muroran Institute of
Technology, Mizumoto 27-1, Muroran, Hokkaido, 050–8585, Japan
<EMAIL_ADDRESS>
###### Abstract.

A linear-interval order is the intersection of a linear order and an interval
order. For this class of orders, several structural results have been known.
This paper introduces a new subclass of linear-interval orders. We call a
partial order a _linear-semiorder_ if it is the intersection of a linear order
and a semiorder. We show a characterization and a polynomial-time recognition
algorithm for linear-semiorders. We also prove that being a linear-semiorder
is a comparability invariant, showing that incomparability graphs of linear-
semiorders can be recognized in polynomial time.

###### Key words and phrases:

Comparability invariant, Linear-interval orders, PI graphs, Recognition
algorithm, Semiorders, Triangle orders, Vertex ordering characterization

###### 2010 Mathematics Subject Classification:

05C62, 05C75, 68R10, 06A07

##  1\. Introduction

A graph is an _intersection graph_ if there is a set of objects such that each
vertex corresponds to an object and two vertices are adjacent if and only if
the corresponding objects have a nonempty intersection. The set of objects is
called a _representation_ of the graph. Intersection graphs of geometric
objects have been widely investigated because of their interesting structures
and applications [5, 13, 23].

Well-known examples of intersection graphs are interval graphs and permutation
graphs. An _interval graph_ is the intersection graph of intervals on the real
line. Let $L_{1}$ and $L_{2}$ be two horizontal lines in the $xy$-plane with
$L_{1}$ above $L_{2}$. A _permutation graph_ is the intersection graph of line
segments joining a point on $L_{1}$ and a point on $L_{2}$.

A common generalization of the two graph classes is trapezoid graphs [8, 9].
An interval on $L_{1}$ and an interval on $L_{2}$ define a trapezoid between
$L_{1}$ and $L_{2}$. A _trapezoid graph_ is the intersection graph of such
trapezoids. The structure of trapezoid graphs is well investigated, and
several recognition algorithms are presented [15, 20, 23].

There is some correspondence between partial orders and intersection graphs of
geometric objects between the two lines [14], [15, Theorem 1.11]. A partial
order $P$ on a set $V$ is a _trapezoid order_ if for each element $v\in V$,
there is a trapezoid $T(v)$ between $L_{1}$ and $L_{2}$ such that for any two
elements $u,v\in V$, we have that $u\prec v$ in $P$ if and only if $T(u)$ lies
completely to the left of $T(v)$. The set of trapezoids $\\{T(v)\colon\ v\in
V\\}$ is called a _trapezoid representation_ of $P$.

By restricting trapezoids in the representation, many order classes have been
introduced [2, 3, 21]. An _up-triangle order_ [2] is a partial order
representable by triangles spanned by a point on $L_{1}$ and an interval on
$L_{2}$. An up-triangle order is also known as a _PI order_ [5, 6, 8], where
_PI_ stands for _point-interval_ , and as a _linear-interval order_ [19]
because it is the intersection of a linear order and an interval order. We use
the term linear-interval orders to denote such orders. Several structural
results have been shown for this order class [6, 8, 25], including polynomial-
time recognition algorithms [19, 27, 26]. As noted in [19], this is one of the
first results for recognizing orders that are the intersection of orders from
different classes.

This paper deals with up-triangle orders representable by triangles spanned by
a point on $L_{1}$ and a _unit-length_ interval on $L_{2}$ (Fig. 1). Such an
order is the intersection of a linear order and a semiorder; hence we call it
a _linear-semiorder_. In Section 3, we show a characterization of linear-
semiorders in terms of linear extensions. We then propose a polynomial-time
recognition algorithm for linear-semiorders in Section 4. In Section 5, we
prove that being a linear-semiorder is a comparability invariant, showing that
incomparability graphs of linear-semiorders can also be recognized in
polynomial time. In Section 6, we show two byproducts of the characterization.
We finally discuss our results and further research in Section 7.

$a$$b$$c$$e$$d$$f$ (a) $a$$b$$c$$d$$e$$f$$L_{1}$$L_{2}$ (b)

Figure 1. A partial order (the dual of chevron) with a triangle
representation.

##  2\. Preliminaries

A (strict) _partially ordered set_ is a pair $(V,P)$, where $V$ is a set and
$P$ is a binary relation on $V$ that is irreflexive, transitive, and therefore
asymmetric. The set $V$ is called a _ground set_ and the relation $P$ is
called a (strict) _partial order_ on $V$. In this paper, we will deal only
with partial orders on finite sets.

We denote partial orders by $\prec$ instead of $P$, that is, we write $u\prec
v$ in $P$ if $(u,v)\in P$. Two elements $u,v\in V$ are _comparable_ in $P$ if
$u\prec v$ or $u\succ v$; otherwise $u$ and $v$ are _incomparable_ , denoted
by $u\parallel v$. A partial order $P$ on a set $V$ is a _linear order_ if any
two distinct elements of $V$ are comparable in $P$.

A partial order $P$ on a set $V$ is an _interval order_ if for each element
$v\in V$, there is a (closed) interval $I(v)$ on the real line such that for
any two elements $u,v\in V$, we have that $u\prec v$ in $P$ if and only if
$I(u)$ lies completely to the left of $I(v)$. Here, the interval
$I(u)=[l(u),r(u)]$ _lies completely to the left of_ $I(v)=[l(v),r(v)]$, and we
write $I(u)\ll I(v)$, if $r(u)<l(v)$. The set of intervals $\\{I(v)\colon\
v\in V\\}$ is called an _interval representation_ of $P$.

An interval representation is _unit_ if every interval has unit length, and it
is _proper_ if no interval properly contains another. An interval order is a
_semiorder_ if it has a unit interval representation. It is known that a
partial order is a semiorder if and only if it has a proper interval
representation [4].

Let $P_{1}$ and $P_{2}$ be two partial orders on the same ground set $V$. The
_intersection_ of $P_{1}$ and $P_{2}$ is the partial order $P=P_{1}\cap
P_{2}$. Equivalently, the intersection of $P_{1}$ and $P_{2}$ is the partial
order $P$ on $V$ such that $u\prec v$ in $P$ if and only if $u\prec v$ in both
$P_{1}$ and $P_{2}$. We call an order a _linear-semiorder_ if it is the
intersection of a linear order and a semiorder.

In addition to partially ordered sets, this paper deals with graphs. All
graphs in this paper are finite with no loops or multiple edges. Unless stated
otherwise, graphs are assumed to be undirected, but we also deal with graphs
with directed edges. We write $uv$ for the _undirected edge_ joining two
vertices $u$ and $v$ and write $(u,v)$ for the _directed edge_ from $u$ to
$v$. For a graph $G=(V,E)$, we sometimes write $V(G)$ for the vertex set $V$
and write $E(G)$ for the edge set $E$.

Let $P$ be a partial order on a set $V$. The _comparability graph_ of $P$ is
the graph $G$ such that $uv\in E(G)$ if and only if $u$ and $v$ are comparable
in $P$. The _incomparability graph_ of $P$ is the graph $G$ such that $uv\in
E(G)$ if and only if $u\parallel v$ in $P$. Note that the incomparability
graph of $P$ is the complement of the comparability graph of $P$, where the
_complement_ of a graph $G$ is the graph $\overline{G}$ such that
$V(\overline{G})=V(G)$ and $uv\in E(\overline{G})$ if and only if $uv\notin
E(G)$ for any two vertices $u,v\in V(\overline{G})$.

Let $G$ be a graph, and let $E\subseteq E(G)$ be a set of (undirected) edges
of $G$. We call a set $F$ of directed edges an _orientation_ of $E$ if $F$ is
obtained from $E$ by orienting each edge of $E$, that is, replacing each edge
$uv\in E$ with either $(u,v)$ or $(v,u)$. An orientation of $G$ is an
orientation of $E(G)$. An orientation $F$ of $G$ is _transitive_ if $(u,v)\in
F$ and $(v,w)\in F$ then $(u,w)\in F$ for any three vertices $u,v,w\in V(G)$.
Note that a partial order $P$ on a set $V$ can be viewed as a transitive
orientation $F$ of the comparability graph of $P$, in which $(u,v)\in F$ if
and only if $u\prec v$ in $P$. We also note that a graph is a comparability
graph if and only if it has a transitive orientation.

A linear-time algorithm is known for computing a transitive orientation of a
comparability graph [18]. However, the algorithm might produce an orientation
that is not transitive if the given graph is not a comparability graph. Thus,
to recognize comparability graphs, we must verify the transitivity after
computing the orientation.

An orientation $F$ of a graph $G$ is _quasi-transitive_ if $(u,v)\in F$ and
$(v,w)\in F$ then $uw\in E(G)$, that is, either $(u,w)\in F$ or $(w,u)\in F$.
In other words, an orientation $F$ of $G$ is quasi-transitive if for any three
vertices $u,v,w\in V$ with $uv,vw\in E(G)$ and $uw\notin E(G)$, either
$(u,v),(w,v)\in F$ or $(v,u),(v,w)\in F$. We can see that an orientation is
transitive if and only if it is quasi-transitive and acyclic.

The linear-time algorithm [18] produces a linear extension of an orientation
$F$ of a given graph $G$ such that $F$ is transitive if $G$ is a comparability
graph. Obviously, $F$ is acyclic. We can test whether $F$ is quasi-transitive
by checking either $(u,v),(w,v)\in F$ or $(v,u),(v,w)\in F$ for any pair of a
non-edge $uw\notin E(G)$ and a vertex $v\in V(G)$ with $uv,vw\in E(G)$. Thus
we have the following.

######  Proposition 1.

Comparability graphs can be recognized in $O(n\bar{m})$ time, where $n$ and
$\bar{m}$ are the number of vertices and non-edges of the given graph. A
transitive orientation of a graph $G$ can be obtained in the same time bound
if $G$ is a comparability graph.

Let $G$ be a graph. A sequence of four vertices $(v_{0},v_{1},v_{2},v_{3})$ is
an _induced cycle of length $4$_ if
$v_{0}v_{1},v_{1}v_{2},v_{2}v_{3},v_{3}v_{0}\in E(G)$ and
$v_{0}v_{2},v_{1}v_{3}\notin E(G)$, denoted by $C_{4}$. A graph consisting of
four vertices $v_{0},v_{1},v_{2},v_{3}$ is a _claw_ if
$v_{0}v_{1},v_{0}v_{2},v_{0}v_{3}\in E(G)$ and
$v_{1}v_{2},v_{2}v_{3},v_{3}v_{1}\notin E(G)$, denoted by $K_{1,3}$. A
sequence of three vertices $(v_{0},v_{1},v_{2})$ is an _induced path of length
$2$_ if $v_{0}v_{1},v_{1}v_{2}\in E(G)$ and $v_{0}v_{2}\notin E(G)$, denoted
by $P_{3}$.

##  3\. Characterization

Let $P$ be a partial order on a set $V$. A linear order $L$ on $V$ is a
_linear extension_ of $P$ if $u\prec v$ in $L$ whenever $u\prec v$ in $P$.
Hence, a linear extension $L$ of $P$ has all the relations of $P$ with
additional relations making $L$ linear. We define some properties of linear
extensions.

The order $\mathbf{2+2}$ of $P$ is a partial order consisting of four elements
$x$, $y$, $z$, $w$ of $V$ such that $x\prec y$ and $z\prec w$ whereas
$x\parallel w$ and $z\parallel y$ in $P$. Note that $x\parallel z$ and
$y\parallel w$ in $P$; otherwise, we would have $x\prec w$ or $z\prec y$ in
$P$. We say that a linear extension $L$ of $P$ fulfills the _$\mathbf{2+2}$
rule_ if $y\prec z$ or $w\prec x$ in $L$ for each induced suborder
$\mathbf{2+2}$ of $P$. If $y\prec z$ in $L$ then $x\prec y\prec z\prec w$ in
$L$; if $w\prec x$ in $L$ then $z\prec w\prec x\prec y$ in $L$. Equivalently,
a linear extension $L$ of $P$ fulfills the $\mathbf{2+2}$ rule if there are no
four elements $x,y,z,w$ of $V$ such that $x\prec y$, $z\prec w$, $x\parallel
w$, and $z\parallel y$ in $P$ whereas $x\prec w$ and $z\prec y$ in $L$ (Fig.
22(a)). We call such an induced suborder a _forbidden configuration for
$\mathbf{2+2}$_.

The order $\mathbf{3+1}$ of $P$ is a partial order consisting of four elements
$x$, $y$, $z$, $w$ of $V$ such that $x\prec y\prec z$ whereas $x\parallel w$
and $w\parallel z$ in $P$. Note that $y\parallel w$ in $P$; otherwise, we
would have $x\prec w$ or $w\prec z$ in $P$. We say that a linear extension $L$
of $P$ fulfills the _$\mathbf{3+1}$ rule_ if $w\prec x$ or $z\prec w$ in $L$
for each induced suborder $\mathbf{3+1}$ of $P$. If $w\prec x$ in $L$ then
$w\prec x\prec y\prec z$ in $L$; if $z\prec w$ in $L$ then $x\prec y\prec
z\prec w$ in $L$. Equivalently, a linear extension $L$ of $P$ fulfills the
$\mathbf{3+1}$ rule if there are no four elements $x,y,z,w$ of $V$ such that
$x\prec y\prec z$, $x\parallel w$, and $w\parallel z$ in $P$ whereas $x\prec
w\prec z$ in $L$ (Fig. 22(b)). We call such an induced suborder a _forbidden
configuration for $\mathbf{3+1}$_.

$x$$y$$z$$w$ (a) $x$$y$$z$$w$ (b) $x$$y$$z$ (c)

Figure 2.  (a) A forbidden configuration for $\mathbf{2+2}$. (b) A forbidden
configuration for $\mathbf{3+1}$. (c) A partial order with $(x,y),(y,z)\in
P\cup R_{1}\cup R_{2}$ but $(x,z)\notin P\cup R_{1}\cup R_{2}$. An arrow $u\to
v$ denotes that $u\prec v$ in $P$; a dashed arrow $u\dasharrow v$ denotes that
$u\prec v$ in $L$ but $u\parallel v$ in $P$.

Note that the orders $\mathbf{2+2}$ and $\mathbf{3+1}$ characterize interval
orders and semiorders as follows. A partial order is an interval order if and
only if it does not contain $\mathbf{2+2}$ as an induced suborder [11]. A
partial order is a semiorder if and only if it does not contain $\mathbf{2+2}$
or $\mathbf{3+1}$ as an induced suborder [22].

Our previous work [25] shows that a partial order is a linear-interval order
if and only if it has a linear extension fulfilling the $\mathbf{2+2}$ rule.
In this paper, we show the following characterization for linear-semiorders.

######  Theorem 2.

A partial order is a linear-semiorder if and only if it has a linear extension
fulfilling the $\mathbf{2+2}$ and $\mathbf{3+1}$ rules.

###### Proof.

The necessity and sufficiency follow immediately from Lemmas 3 and 4,
respectively. ∎

######  Lemma 3.

If a partial order $P$ on a set $V$ has a linear order $L$ and a semiorder $S$
with $L\cap S=P$, then $L$ is a linear extension of $P$ fulfilling the
$\mathbf{2+2}$ and $\mathbf{3+1}$ rules.

###### Proof.

The linear order $L$ can be viewed as a linear extension of $P$. It is shown
in [8, 25] that $L$ fulfills the $\mathbf{2+2}$ rule. We now show that $L$
fulfills the $\mathbf{3+1}$ rule. Suppose that $L$ has a forbidden
configuration for $\mathbf{3+1}$ consisting of four elements $x,y,z,w$ of $V$
such that $x\prec y\prec z$, $x\parallel w$, and $z\parallel w$ in $P$ whereas
$x\prec w\prec z$ in $L$. Let $\\{I(v)\colon\ v\in V\\}$ be a proper interval
representation of the semiorder $S$, and let $I(v)=[l(v),r(v)]$ for each
element $v$ of $V$. Since $x\prec y\prec z$ in $P$, we have $r(x)<l(y)\leq
r(y)<l(z)$. Since $x\prec w$ in $L$ and $x\parallel w$ in $P$, we have
$x\not\prec w$ in $S$. Thus $l(w)\leq r(x)$. Similarly, since $w\prec z$ in
$L$ and $w\parallel z$ in $P$, we have $w\not\prec z$ in $S$. Thus $l(z)\leq
r(w)$. Therefore, $I(w)\supseteq I(y)$, contradicting that no interval
properly contains another. ∎

######  Lemma 4.

If a partial order $P$ on a set $V$ has a linear extension $L$ fulfilling the
$\mathbf{2+2}$ and $\mathbf{3+1}$ rules, then there is a semiorder $S$ with
$L\cap S=P$. The semiorder $S$ and its proper interval representation can be
obtained in $O(n^{3})$ time, where $n$ is the number of elements of $V$.

###### Proof.

In this proof, we denote partial orders as a set of ordered pairs of elements.
For example, we write $(u,v)\in P$ if $u\prec v$ in $P$, and write $(u,v)\in
L-P$ if $u\parallel v$ in $P$ and $u\prec v$ in $L$.

We define the following two binary relations on $V$.

$\displaystyle R_{1}$ $\displaystyle=\\{(x,y)\in V^{2}\colon\ \text{there is
an element $z\in V$ with $(x,z)\in P$ and $(y,z)\in L-P$}\\};$ $\displaystyle
R_{2}$ $\displaystyle=\\{(x,y)\in V^{2}\colon\ \text{there is an element $z\in
V$ with $(z,x)\in L-P$ and $(z,y)\in P$}\\}.$

Let $Q=P\cup R_{1}\cup R_{2}$. Note that the relation $Q$ is not necessarily
transitive. See a partial order in Fig. 22(c). We have $(x,y)\in R_{2}$ and
$(y,z)\in R_{1}$, but $(x,z)\notin P\cup R_{1}\cup R_{2}$.

######  Claim 1.

There is a linear order $L_{Q}$ on $V$ such that $x\prec y$ in $L_{Q}$
whenever $(x,y)\in Q$.

###### Proof of Claim 1.

We say that a sequence of distinct elements $(v_{0},v_{1},\ldots,v_{k-1})$ of
$V$ is a _cycle_ of $Q$ if $(v_{i},v_{i+1})\in Q$ for every index $i$ with
$0\leq i<k$ (indices are modulo $k$). The _length_ of the cycle is the number
$k$. To prove the claim, we show by a case analysis that $Q$ has no cycles.

Suppose that $Q$ has a cycle of length 2. We first suppose $(v_{0},v_{1})\in
R_{1}$. Then there is an element $u\in V$ with $(v_{0},u)\in P$ and
$(v_{1},u)\in L-P$. If $(v_{1},v_{0})\in P$ then $(v_{0},u)\in P$ implies
$(v_{1},u)\in P$, a contradiction. If $(v_{1},v_{0})\in R_{1}$ then there is
an element $w\in V$ with $(v_{1},w)\in P$ and $(v_{0},w)\in L-S$. Thus $L$ has
a forbidden configuration for $\mathbf{2+2}$, a contradiction. If
$(v_{1},v_{0})\in R_{2}$ then there is an elements $w\in V$ with $(w,v_{0})\in
P$ and $(w,v_{1})\in L-S$. Thus $L$ has a forbidden configuration for
$\mathbf{3+1}$, a contradiction. Therefore, $(v_{0},v_{1})\notin R_{1}$. A
similar argument would show $(v_{0},v_{1})\notin R_{2}$. We finally suppose
$(v_{0},v_{1})\in P$. Trivially, $(v_{1},v_{0})\notin P$. We also have
$(v_{1},v_{0})\notin R_{1}$ and $(v_{1},v_{0})\notin R_{2}$ by symmetric
arguments. Thus $(v_{0},v_{1})\notin P$. Therefore, $Q$ has no cycles of
length 2.

Suppose that $Q$ has a cycle of length greater than 2. Let
$(v_{0},v_{1},\ldots,v_{k-1})$ be such a cycle with minimal length, that is,
there are no relations $(v_{i},v_{j})\in Q$ with $j\neq i+1$. Suppose further
that there is an index $i$ with $(v_{i},v_{i+1})\in P$. If
$(v_{i+1},v_{i+2})\in P$ then $(v_{i},v_{i+2})\in P$, a contradiction. Suppose
$(v_{i+1},v_{i+2})\in R_{1}$. Then there is an element $u\in V$ with
$(v_{i+1},u)\in P$ and $(v_{i+2},u)\in L-P$. We have $(v_{i},u)\in P$ from
$(v_{i},v_{i+1}),(v_{i+1},u)\in P$. Now $(v_{i},u)\in P$ and $(v_{i+2},u)\in
L-P$ imply $(v_{i},v_{i+2})\in R_{1}$, a contradiction. Suppose
$(v_{i+1},v_{i+2})\in R_{2}$. Then there is an element $u\in V$ with
$(u,v_{i+1})\in L-P$ and $(u,v_{i+2})\in P$. We have that $v_{i}\parallel
v_{i+2}$ in $P$; otherwise, $(v_{i},v_{i+2})\in Q$ or $(v_{i+2},v_{i})\in Q$,
a contradiction. Thus the elements $u,v_{i+2},v_{i},v_{i+1}$ induce
$\mathbf{2+2}$. Since $L$ fulfills the $\mathbf{2+2}$ rule and $(u,v_{i+1})\in
L-P$, we have $(u,v_{i})\in L-P$. Now $(u,v_{i})\in L-P$ and $(u,v_{i+2})\in
P$ imply $(v_{i},v_{i+2})\in R_{2}$, a contradiction. Therefore, there is no
index $i$ with $(v_{i},v_{i+1})\in P$.

Suppose there is an index $i$ with $(v_{i},v_{i+1}),(v_{i+1},v_{i+2})\in
R_{1}$. Then there are two elements $u_{0},u_{1}\in V$ with
$(v_{i},u_{0}),(v_{i+1},u_{1})\in P$ and $(v_{i+1},u_{0}),(v_{i+2},u_{1})\in
L-S$. If $(v_{i},u_{1})\in P$ then $(v_{i+2},u_{1})\in L-P$ implies
$(v_{i},v_{i+2})\in R_{1}$, a contradiction. If $(v_{i},u_{1})\in L-P$ then
the elements $v_{i},u_{0},v_{i+1},u_{1}$ induce a forbidden configuration for
$\mathbf{2+2}$, a contradiction. Thus $(u_{1},v_{i})\in L$, and we have
$(v_{i+2},u_{0})\in L$ from $(v_{i+2},u_{1}),(u_{1},v_{i}),(v_{i},u_{0})\in
L$. If $(v_{i+2},u_{0})\in P$ then the elements $v_{i+2},u_{0},v_{i+1},u_{1}$
induce a forbidden configuration for $\mathbf{2+2}$, a contradiction. If
$(v_{i+2},u_{0})\in L-P$ then $(v_{i},u_{0})\in P$ implies $(v_{i},v_{i+2})\in
R_{1}$, a contradiction. Therefore, there is no index $i$ with
$(v_{i},v_{i+1}),(v_{i+1},v_{i+2})\in R_{1}$. A similar argument would show
that there is no index $i$ with $(v_{i},v_{i+1}),(v_{i+1},v_{i+2})\in R_{2}$.

Now, there is an index $i$ with $(v_{i},v_{i+1})\in R_{1}$; hence
$(v_{i+1},v_{i+2})\in R_{2}$ and $(v_{i+2},v_{i+3})\in R_{1}$. Note that the
vertices $v_{i},v_{i+1},v_{i+2}$ are distinct by assumption, but $v_{i+3}$
could be identical to $v_{1}$. Then there are three elements
$u_{0},u_{1},u_{2}\in V$ with
$(v_{i},u_{0}),(u_{1},v_{i+2}),(v_{i+2},u_{2})\in P$ and
$(v_{i+1},u_{0}),(u_{1},v_{i+1}),(v_{i+3},u_{2})\in L-P$. We have $u_{0}\neq
u_{2}$; otherwise, the elements $u_{1},v_{i+2},u_{2}=u_{0},v_{i+1}$ induce a
forbidden configuration for $\mathbf{3+1}$, a contradiction. If
$(v_{i+2},u_{0})\in P$ then the elements $u_{1},v_{i+2},u_{0},v_{i+1}$ induce
a forbidden configuration for $\mathbf{3+1}$, a contradiction. If
$(v_{i+2},u_{0})\in L-P$ then $(v_{i},u_{0})\in P$ implies $(v_{i},v_{i+2})\in
R_{1}$, a contradiction. Thus $(u_{0},v_{i+2})\in L$, and we have
$(v_{i+1},u_{2})\in L$ from
$(v_{i+1},u_{0}),(u_{0},v_{i+2}),(v_{i+2},u_{2})\in L$. If $(v_{i+1},u_{2})\in
P$ then $(v_{i+3},u_{2})\in L-P$ implies $(v_{i+1},v_{i+3})\in R_{1}$, a
contradiction. If $(v_{i+1},u_{2})\in L-P$ then the elements
$u_{1},v_{i+2},u_{2},v_{i+1}$ induce a forbidden configuration for
$\mathbf{3+1}$, a contradiction.

Therefore, the relation $Q$ has no cycles, and thus the claim holds. ∎

Assume that the elements $v_{1},v_{2},\ldots,v_{n}$ of $V$ are indexed so that
$i<j$ if $v_{i}\prec v_{j}$ in $L_{Q}$.

######  Claim 2.

The elements $v_{1},v_{2},\ldots,v_{n}$ satisfies the following properties:

  1. (a)

There are no three indices $i,j,k$ with $i<j<k$ such that $(v_{i},v_{k})\in
L-P$ and $(v_{j},v_{k})\in P$.

  2. (b)

There are no three indices $i,j,k$ with $i<j<k$ such that $(v_{i},v_{k})\in
L-P$ and $(v_{i},v_{j})\in P$.

  3. (c)

There are no four indices $i,j,k,h$ with $i<j<k<h$ such that $(v_{i},v_{h})\in
L-P$ and $(v_{j},v_{k})\in P$.

###### Proof of Claim 2.

Suppose there are three indices $i,j,k$ with $i<j<k$ such that
$(v_{i},v_{k})\in L-P$ and $(v_{j},v_{k})\in P$. Then $(v_{j},v_{i})\in
R_{1}$, which implies $v_{j}\prec v_{i}$ in $L_{Q}$, a contradiction. Thus the
property (a) holds. Suppose there are three indices $i,j,k$ with $i<j<k$ such
that $(v_{i},v_{k})\in L-P$ and $(v_{i},v_{j})\in P$. Then $(v_{k},v_{j})\in
R_{2}$, which implies $v_{k}\prec v_{j}$ in $L_{Q}$, a contradiction. Thus the
property (b) holds.

Suppose there are four indices $i,j,k,h$ with $i<j<k<h$ such that
$(v_{i},v_{h})\in L-P$ and $(v_{j},v_{k})\in P$. If $(v_{i},v_{k})\in P$ then
the indices $i,k,h$ satisfy $i<k<h$ with $(v_{i},v_{h})\in L-P$ and
$(v_{i},v_{k})\in P$, contradicting the property (b). If $(v_{i},v_{k})\in
L-P$ then the indices $i,j,k$ satisfy $i<j<k$ with $(v_{i},v_{k})\in L-P$ and
$(v_{j},v_{k})\in P$, contradicting the property (a). Thus $(v_{k},v_{i})\in
L$. A similar argument would show $(v_{h},v_{j})\in L$. Then
$(v_{i},v_{h}),(v_{h},v_{j}),(v_{j},v_{k}),(v_{k},v_{i})\in L$, a
contradiction. Thus the property (c) holds. ∎

We define a function $f:\\{1,2,\ldots,n\\}\to\mathbb{N}$ recursively as
follows. For the base case, we set $f(1)=0$; for each index $j$ with $1<j\leq
n$, we set

$f(j)=\begin{cases}\max\\{i\colon\ \text{$f(j-1)<i$ and $(v_{i},v_{j})\in
P$}\\}&\text{if there is an index $i$ with $f(j-1)<i$ and $(v_{i},v_{j})\in
P$, }\\\ f(j-1)&\text{otherwise. }\end{cases}$

######  Claim 3.

The function $f$ satisfies the following properties:

  1. (a)

$0\leq f(i)<i$.

  2. (b)

If $i<j$ then $f(i)\leq f(j)$.

  3. (c)

If $(v_{i},v_{j})\in P$ then $i\leq f(j)$.

  4. (d)

If $(v_{i},v_{j})\in L-P$ then $f(j)<i$.

###### Proof of Claim 3.

Trivially, $f$ satisfies the properties (a)–(c). Suppose there are two indices
$i$ and $j$ with $(v_{i},v_{j})\in L-P$ and $i\leq f(j)$. If
$(v_{f(j)},v_{j})\in P$ then $i\neq f(j)$, that is, $i<f(j)$. Hence the
indices $i,f(j),j$ satisfy $i<f(j)<j$ with $(v_{i},v_{j})\in L-P$ and
$(v_{f(j)},v_{j})\in P$, contradicting the property (a) of Claim 2. If
$(v_{f(j)},v_{j})\notin P$ then from the definition of $f$, there is an index
$k$ with $k<j$ such that $f(k)=f(j)$ and $(v_{f(k)},v_{k})\in P$. Then $i\leq
f(j)=f(k)<k<j$ with $(v_{i},v_{j})\in L-P$ and $(v_{f(k)},v_{k})\in P$,
contradicting the property (b) or (c) of Claim 2. Therefore, $f$ satisfies the
property (d). ∎

Let $\mathcal{I}=\\{[f(i)+\frac{i-1}{n},i]\colon\ 1\leq i\leq n\\}$ be the set
of intervals on the real line. The property (a) of Claim 3 ensures that
intervals of $\mathcal{I}$ are well-defined. The property (b) of Claim 3
implies that no interval of $\mathcal{I}$ properly contains another. Let $S$
be the semiorder obtained from the proper interval representation
$\mathcal{I}$. The properties (c) and (d) of Claim 3 imply, respectively, that
$v_{i}\prec v_{j}$ in $S$ if $(v_{i},v_{j})\in P$ and $v_{i}\not\prec v_{j}$
in $S$ if $(v_{i},v_{j})\in L-P$. Therefore, $L\cap S=P$.

The relation $Q$ is obtained in $O(n^{3})$ time from $P$ and $L$. The function
$f$ and the representation $\mathcal{I}$ of $S$ are obtained in $O(n^{2})$
time from $L_{Q}$. Thus $S$ and $\mathcal{I}$ can be obtained from $P$ and $L$
in $O(n^{3})$ time. ∎

In Fig. 3, we illustrate the construction of the semiorder in the proof of
Lemma 4. Consider a partial order $P$ in Fig. 33(a). Figure 1 shows that $P$
is a linear-semiorder. Let $L$ be the linear order with $a\prec b\prec c\prec
d\prec e\prec f$. We can observe that $L$ fulfills the $\mathbf{2+2}$ and
$\mathbf{3+1}$ rules. We have $R_{1}\cup
R_{2}=\\{(a,c),(c,b),(c,e),(e,b),(e,d),(f,d)\\}$. Thus there are two linear
orders that contain all ordered pairs of $Q=P\cup R_{1}\cup R_{2}$, that is, a
linear order with $a\prec c\prec e\prec b\prec f\prec d$ and a linear order
with $a\prec c\prec e\prec f\prec b\prec d$. We choose the latter as $L_{Q}$.
We obtain the six intervals $I(a)=[0,1]$, $I(c)=[\frac{1}{6},2]$,
$I(e)=[1+\frac{2}{6},3]$, $I(f)=[3+\frac{3}{6},4]$, $I(b)=[3+\frac{4}{6},5]$,
and $I(d)=[5+\frac{5}{6},6]$ (Fig. 33(c)). We can verify that no interval
properly contains another. The semiorder $S$ defined by the intervals is in
Fig. 33(b), and we can observe $L\cap S=P$.

$a$$b$$c$$e$$d$$f$ (a) $a$$c$$e$$f$$b$$d$ (b)
$0$$1$$2$$3$$4$$5$$6$$a$$c$$e$$f$$b$$d$ (c)

Figure 3.  (a) A linear-semiorder $P$. (b) The semiorder $S$. (c) The proper
interval representation of $S$.

##  4\. Recognition algorithm

In this section, we show a recognition algorithm for linear-semiorders. The
following is our main result.

######  Theorem 5.

A linear-semiorder can be recognized in $O(n\bar{m})$ time. A linear extension
fulfilling the $\mathbf{2+2}$ and $\mathbf{3+1}$ rules can be obtained in
$O(m\bar{m}^{2})$ time. Here, $n$, $m$, and $\bar{m}$ are the number of
elements, comparable pairs, and incomparable pairs of the given order,
respectively.

Let $P$ be a partial order on a set $V$, and let $G$ be the comparability
graph of $P$. In this section, we consider $V$ as the vertex set of $G$ and
$P$ as the transitive orientation of $G$. That is, we consider $P$ as the set
of directed edges such that for any three vertices $u,v,w$ of $G$, if
$(u,v),(v,w)\in P$ then $(u,w)\in P$. Note $n=|V|$ and $m=|E(G)|$.

Let $\overline{G}$ be the complement of $G$. Recall that $\overline{G}$ is the
incomparability graph of $P$, and hence $\bar{m}=|E(\overline{G})|$. Let $F$
be an orientation of $\overline{G}$, and let $P+F$ denote the union of
directed edges of $P$ and $F$. Note that $P+F$ is the orientation of the
complete graph on $V$. Thus if $P+F$ is acyclic then $P+F$ can be viewed as
the linear order on $V$.

A _forbidden configuration for $\mathbf{2+2}$_ is a sequence of vertices
$(x,y,z,w)$ with $(x,y),(z,w)\in P$ and $(z,y),(x,w)\in F$ (Fig. 22(a)). A
_forbidden configuration for $\mathbf{3+1}$_ is a sequence of vertices
$(x,y,z,w)$ with $(x,y),(y,z)\in P$ and $(w,z),(x,w)\in F$ (Fig. 22(b)). The
following can be obtained from Theorem 2.

######  Proposition 6.

A partial order $P$ on a set $V$ is a linear-semiorder if and only if there is
an orientation $F$ of the incomparability graph of $P$ such that $P+F$ is
acyclic and contains no forbidden configurations for $\mathbf{2+2}$ or
$\mathbf{3+1}$.

Let $C_{4}$ denote an induced cycle of length 4, and let $K_{1,3}$ denote a
claw. We denote by $E_{o}$ the set of edges of $C_{4}$ or $K_{1,3}$ of
$\overline{G}$. Note $E_{o}\subseteq E(\overline{G})$ by definition. The
proposed algorithm orients the edges of $E_{o}$, instead of the edges of
$\overline{G}$. In the following, we say that even if $F$ is an orientation of
not all edges of $\overline{G}$, a sequence of vertices $(x,y,z,w)$ is a
forbidden configuration for $\mathbf{2+2}$ if $(x,y),(z,w)\in P$ and
$(z,y),(x,w)\in F$. Similarly, we say that $(x,y,z,w)$ is a forbidden
configuration for $\mathbf{3+1}$ if $(x,y),(y,z)\in P$ and $(w,z),(x,w)\in F$.

######  Lemma 7.

A partial order $P$ on a set $V$ is a linear-semiorder if and only if there is
an orientation $F$ of $E_{o}$ such that $P+F$ is acyclic and contains no
forbidden configurations for $\mathbf{2+2}$ or $\mathbf{3+1}$. If the
orientation $F$ exists, every linear extension of $P+F$ fulfills the
$\mathbf{2+2}$ and $\mathbf{3+1}$ rules.

Before proving Lemma 7, we show the following two observations.

######  Proposition 8.

Let $x$, $y$, $z$, $w$ be four vertices of $V$. If $(x,y),(z,w)\in P$ and
$xw,yz\in E(\overline{G})$ then $xz,yw\in E(\overline{G})$, that is,
$(x,z,y,w)$ is $C_{4}$ of $\overline{G}$.

###### Proof.

If $(x,z)\in P$ then $(z,w)\in P$ implies $(x,w)\in P$, contradicting $xw\in
E(\overline{G})$. If $(z,x)\in P$ then $(x,y)\in P$ implies $(z,y)\in P$,
contradicting $yz\in E(\overline{G})$. Thus $xz\in E(\overline{G})$.
Similarly, we have $yw\in E(\overline{G})$. ∎

######  Proposition 9.

Let $x$, $y$, $z$, $w$ be four vertices of $V$. If $(x,y),(y,z)\in P$ and
$xw,zw\in E(\overline{G})$ then $yw\in E(\overline{G})$, that is, the four
vertices induce $K_{1,3}$ of $\overline{G}$.

###### Proof.

If $(y,w)\in P$ then $(x,y)\in P$ implies $(x,w)\in P$, contradicting $xw\in
E(\overline{G})$. If $(w,y)\in P$ then $(y,z)\in P$ implies $(w,z)\in P$,
contradicting $zw\in E(\overline{G})$. Thus $yw\in E(\overline{G})$. ∎

###### Proof of Lemma 7.

The necessity is trivial from Proposition 6. We now show the sufficiency. Let
$F$ be an orientation of $E_{o}$ such that $P+F$ is acyclic and contains no
forbidden configurations for $\mathbf{2+2}$ or $\mathbf{3+1}$. Let $L$ be a
linear extension of $P+F$, and let $F^{\prime}=L-P$. Note that $F^{\prime}$ is
an orientation of $\overline{G}$ and $F^{\prime}\supseteq F$. Suppose that
$P+F^{\prime}$ contains a forbidden configuration for $\mathbf{2+2}$, that is,
there is a sequence of vertices $(x,y,z,w)$ with $(x,y),(z,w)\in P$ and
$(z,y),(x,w)\in F^{\prime}$. Since $xw,yz\in E(\overline{G})$, Proposition 8
implies that $(x,z,y,w)$ is $C_{4}$ of $\overline{G}$. Thus $xw,yz\in E_{o}$.
Since $F\subseteq F^{\prime}$, we have $(z,y),(x,w)\in F$, contradicting that
$P+F$ contains no forbidden configurations for $\mathbf{2+2}$. Similarly, when
we suppose that $P+F^{\prime}$ contains a forbidden configuration for
$\mathbf{3+1}$, we have a contradiction from Proposition 9. ∎

The order $\mathbf{2+1}$ of $P$ is the partial order consisting of three
elements $x$, $y$, $z$ of $V$ such that $x\prec y$ whereas $x\parallel z$ and
$y\parallel z$ in $P$. A _forbidden configuration for $\mathbf{2+1}$_ is a
sequence of vertices $(x,y,z)$ with $(x,y)\in P$ and $(y,z),(z,x)\in F$.

If $P+F$ is acyclic then $P+F$ contains no forbidden configurations for
$\mathbf{2+1}$. We show in Theorem 18 that if $P+F$ contains no forbidden
configurations for $\mathbf{2+2}$, $\mathbf{3+1}$, or $\mathbf{2+1}$, then
even if $P+F$ is not acyclic, there is an orientation $F^{\prime}$ of $E_{o}$
such that $P+F^{\prime}$ is acyclic and contains no forbidden configurations
for $\mathbf{2+2}$ or $\mathbf{3+1}$.

######  Lemma 10.

We can compute in $O(n\bar{m})$ time an orientation $F$ of $E_{o}$ such that
$P+F$ contains no forbidden configurations for $\mathbf{2+2}$, $\mathbf{3+1}$,
or $\mathbf{2+1}$.

We show two observations to prove Lemma 10.

######  Proposition 11.

Let $F$ be an orientation of $E_{o}$ such that $P+F$ contains no forbidden
configurations for $\mathbf{2+1}$. The orientation $P+F$ contains no forbidden
configurations for $\mathbf{2+2}$ if and only if for any $C_{4}=(x,y,z,w)$ of
$\overline{G}$, either $(x,y),(z,y),(z,w),(x,w)\in F$ or
$(y,x),(y,z),(w,z),(w,x)\in F$.

###### Proof.

The sufficiency is trivial. We now show the necessity. Assume without loss of
generality $(x,z),(y,w)\in P$. Suppose $(x,y)\in F$. If $(w,x)\in F$ then
$(y,w,x)$ is a forbidden configuration for $\mathbf{2+1}$, a contradiction.
Thus $(x,w)\in F$. If $(y,z)\in F$ then $(x,z,y,w)$ is a forbidden
configuration for $\mathbf{2+2}$, a contradiction. Thus $(z,y)\in F$. If
$(w,z)\in F$ then $(y,w,z)$ is a forbidden configuration for $\mathbf{2+1}$, a
contradiction. Thus $(z,w)\in F$.

Conversely, suppose $(y,x)\in F$. If $(z,y)\in F$ then $(x,z,y)$ is a
forbidden configuration for $\mathbf{2+1}$, a contradiction. Thus $(y,z)\in
F$. If $(x,w)\in F$ then $(y,w,x,z)$ is a forbidden configuration for
$\mathbf{2+2}$, a contradiction. Thus $(w,x)\in F$. If $(z,w)\in F$ then
$(x,z,w)$ is a forbidden configuration for $\mathbf{2+1}$, a contradiction.
Thus $(w,z)\in F$. ∎

######  Proposition 12.

Let $F$ be an orientation of $E_{o}$ such that $P+F$ contains no forbidden
configurations for $\mathbf{2+1}$. The orientation $P+F$ contains no forbidden
configurations for $\mathbf{3+1}$ if and only if for any $K_{1,3}$ of
$\overline{G}$ consisting of $x,y,z,w\in V$ with $xw,yw,zw\in
E(\overline{G})$, either $(x,w),(y,w),(z,w)\in F$ or $(w,x),(w,y),(w,z)\in F$.

###### Proof.

The sufficiency is trivial. We now show the necessity. Assume without loss of
generality $(x,y),(y,z)\in P$. Suppose $(x,w)\in F$. If $(w,z)\in F$ then
$(x,y,z,w)$ is a forbidden configuration for $\mathbf{3+1}$, a contradiction.
Thus $(z,w)\in F$. If $(w,y)\in F$ then $(y,z,w)$ is a forbidden configuration
for $\mathbf{2+1}$, a contradiction. Thus $(y,w)\in F$.

Conversely, suppose $(w,x)\in F$. If $(y,w)\in F$ then $(x,y,w)$ is a
forbidden configuration for $\mathbf{2+1}$, a contradiction. Thus $(w,y)\in
F$. If $(z,w)\in F$ then $(y,z,w)$ is a forbidden configuration for
$\mathbf{2+1}$, a contradiction. Thus $(w,z)\in F$. ∎

###### Proof of Lemma 10.

The _neighborhood_ of a vertex $v$ of $\overline{G}$ is the set
$N_{\overline{G}}(v)=\\{u\in V\colon\ uv\in E(\overline{G})\\}$. We define
that the _upper set_ of $v\in V$ is the set $U(v)=\\{u\in V\colon\ (v,u)\in
P\\}$ and the _lower set_ of $v\in V$ is the set $L(v)=\\{u\in V\colon\
(u,v)\in P\\}$. We first show a series of claims. Let $uv$ be an edge of
$\overline{G}$.

######  Claim 4.

If $U(u)\cap N_{\overline{G}}(v)\neq\emptyset$ and $N_{\overline{G}}(u)\cap
U(v)\neq\emptyset$, then for any two vertices $w\in U(u)\cap
N_{\overline{G}}(v)$ and $z\in N_{\overline{G}}(u)\cap U(v)$, we have that
$(u,v,w,z)$ is $C_{4}$. Conversely, each $C_{4}$ has an edge $uv$ with
$U(u)\cap N_{\overline{G}}(v)\neq\emptyset$ and $N_{\overline{G}}(u)\cap
U(v)\neq\emptyset$.

###### Proof of Claim 4.

The second claim is trivial. We now show the first claim. If $(w,z)\in P$ then
$(u,w)\in P$ implies $(u,z)\in P$, contradicting $uz\in E(\overline{G})$. If
$(z,w)\in P$ then $(v,z)\in P$ implies $(v,w)\in P$, contradicting $vw\in
E(\overline{G})$. Thus $wz\in E_{\overline{G}}(G)$, that is, $(u,v,w,z)$ is
$C_{4}$. ∎

By a similar argument, we have the following.

######  Claim 5.

If $L(u)\cap N_{\overline{G}}(v)\neq\emptyset$ and $N_{\overline{G}}(u)\cap
L(v)\neq\emptyset$, then for any two vertices $w\in L(u)\cap
N_{\overline{G}}(v)$ and $z\in N_{\overline{G}}(u)\cap L(v)$, we have that
$(u,v,w,z)$ is $C_{4}$. Conversely, each $C_{4}$ has an edge $uv$ with
$L(u)\cap N_{\overline{G}}(v)\neq\emptyset$ and $N_{\overline{G}}(u)\cap
L(v)\neq\emptyset$.

The following is trivial.

######  Claim 6.

If $U(u)\cap N_{\overline{G}}(v)\neq\emptyset$ and $L(u)\cap
N_{\overline{G}}(v)\neq\emptyset$, then for any two vertices $w\in U(u)\cap
N_{\overline{G}}(v)$ and $z\in L(u)\cap N_{\overline{G}}(v)$, the vertices
$z,u,w,v$ induce $K_{1,3}$. Conversely, each $K_{1,3}$ has an edge $uv$ with
$U(u)\cap N_{\overline{G}}(v)\neq\emptyset$ and $L(u)\cap
N_{\overline{G}}(v)\neq\emptyset$.

Therefore, we can compute $E_{o}$ by Algorithm 1. Each iteration on lines 2–23
takes $O(n)$ time for each edge of $\overline{G}$, and hence the running time
is $O(n\bar{m})$.

Input: A partial order $P$ and the incomparability graph $\overline{G}$ of
$P$.

Output: The set $E_{o}$ of edges of $\overline{G}$.

1

2$E_{o}\leftarrow\emptyset$;

3 foreach  _$uv\in E(\overline{G})$_ do

4 if  _$U(u)\cap N_{\overline{G}}(v)\neq\emptyset$ and
$N_{\overline{G}}(u)\cap U(v)\neq\emptyset$_ then

5 $E_{o}\leftarrow E_{o}+uv$;

6 foreach  _$w\in U(u)\cap N_{\overline{G}}(v)$_ do $E_{o}\leftarrow
E_{o}+vw$;

7 foreach  _$z\in N_{\overline{G}}(u)\cap U(v)$_ do $E_{o}\leftarrow
E_{o}+uz$;

8

9 end if

10 if  _$L(u)\cap N_{\overline{G}}(v)\neq\emptyset$ and
$N_{\overline{G}}(u)\cap L(v)\neq\emptyset$_ then

11 $E_{o}\leftarrow E_{o}+uv$;

12 foreach  _$w\in L(u)\cap N_{\overline{G}}(v)$_ do $E_{o}\leftarrow
E_{o}+vw$;

13 foreach  _$z\in N_{\overline{G}}(u)\cap L(v)$_ do $E_{o}\leftarrow
E_{o}+uz$;

14

15 end if

16 if  _$U(u)\cap N_{\overline{G}}(v)\neq\emptyset$ and $L(u)\cap
N_{\overline{G}}(v)\neq\emptyset$_ then

17 $E_{o}\leftarrow E_{o}+uv$;

18 foreach  _$w\in U(u)\cap N_{\overline{G}}(v)$_ do $E_{o}\leftarrow
E_{o}+vw$;

19 foreach  _$z\in L(u)\cap N_{\overline{G}}(v)$_ do $E_{o}\leftarrow
E_{o}+vz$;

20

21 end if

22 if  _$N_{\overline{G}}(u)\cap U(v)\neq\emptyset$ and
$N_{\overline{G}}(u)\cap L(v)\neq\emptyset$_ then

23 $E_{o}\leftarrow E_{o}+uv$;

24 foreach  _$w\in N_{\overline{G}}(u)\cap U(v)$_ do $E_{o}\leftarrow
E_{o}+uw$;

25 foreach  _$z\in N_{\overline{G}}(u)\cap L(v)$_ do $E_{o}\leftarrow
E_{o}+uz$;

26

27 end if

28

29 end foreach

30return _$E_{o}$_ ;

Algorithm 1 Algorithm for computing $E_{o}$

Let $P_{3}$ denote an induced path of length 2. The following is trivial.

######  Claim 7.

If $U(u)\cap N_{\overline{G}}(v)\neq\emptyset$ then for any vertex $w\in
U(u)\cap N_{\overline{G}}(v)$, we have that $(u,v,w)$ is $P_{3}$. Conversely,
each $P_{3}$ has an edge $uv$ with $U(u)\cap
N_{\overline{G}}(v)\neq\emptyset$.

Now, we show an algorithm to find the orientation of $F$ of $E_{o}$ (Algorithm
2). We use the 2-satisfiability problem in the algorithm. An instance of the
2-satisfiability problem is a _2-CNF formula_ , a Boolean formula in
conjunctive normal form with at most two literals per clause. Assume that the
vertices are linearly ordered, and we assign a Boolean variable $x_{(u,v)}$
for each edge $uv$ of $\overline{G}$, where $u$ precedes $v$ in the ordering.
We denote the negation of $x_{(u,v)}$ by $x_{(v,u)}$. The algorithm first
constructs the 2-CNF formula $\varphi$ (lines 1–21), then finds a satisfying
truth assignment $\tau$ of $\varphi$ (line 22), and finally orients each edge
$uv\in E_{o}$ as $(u,v)\in F$ if $x_{(u,v)}=0$ in $\tau$ (line 23).

Input: A partial order $P$ and the set $E_{o}$ of edges of $\overline{G}$.

Output: An orientation $F$ of $E_{o}$ such that $P+F$ contains no forbidden
configurations.

1

2$\varphi\leftarrow\emptyset$;

3 foreach  _$uv\in E_{o}$_ do /* construct the 2-CNF formula $\varphi$ */

4 if  _$U(u)\cap N_{\overline{G}}(v)\neq\emptyset$ and
$N_{\overline{G}}(u)\cap U(v)\neq\emptyset$_ then

5 foreach  _$w\in U(u)\cap N_{\overline{G}}(v)$_ do add the clauses
$(x_{(u,v)}\vee x_{(v,w)})$ and $(x_{(w,v)}\vee x_{(v,u)})$ to $\varphi$;

6 foreach  _$z\in N_{\overline{G}}(u)\cap U(v)$_ do add the clauses
$(x_{(v,u)}\vee x_{(u,z)})$ and $(x_{(z,u)}\vee x_{(u,v)})$ to $\varphi$;

7

8 end if

9 if  _$L(u)\cap N_{\overline{G}}(v)\neq\emptyset$ and
$N_{\overline{G}}(u)\cap L(v)\neq\emptyset$_ then

10 foreach  _$w\in L(u)\cap N_{\overline{G}}(v)$_ do add the clauses
$(x_{(u,v)}\vee x_{(v,w)})$ and $(x_{(w,v)}\vee x_{(v,u)})$ to $\varphi$;

11 foreach  _$z\in N_{\overline{G}}(u)\cap L(v)$_ do add the clauses
$(x_{(v,u)}\vee x_{(u,z)})$ and $(x_{(z,u)}\vee x_{(u,v)})$ to $\varphi$;

12

13 end if

14 if  _$U(u)\cap N_{\overline{G}}(v)\neq\emptyset$ and $L(u)\cap
N_{\overline{G}}(v)\neq\emptyset$_ then

15 foreach  _$w\in U(u)\cap N_{\overline{G}}(v)$_ do add the clauses
$(x_{(u,v)}\vee x_{(v,w)})$ and $(x_{(w,v)}\vee x_{(v,u)})$ to $\varphi$;

16 foreach  _$z\in L(u)\cap N_{\overline{G}}(v)$_ do add the clauses
$(x_{(u,v)}\vee x_{(v,z)})$ and $(x_{(z,v)}\vee x_{(v,u)})$ to $\varphi$;

17

18 end if

19 if  _$N_{\overline{G}}(u)\cap U(v)\neq\emptyset$ and
$N_{\overline{G}}(u)\cap L(v)\neq\emptyset$_ then

20 foreach  _$w\in N_{\overline{G}}(u)\cap U(v)$_ do add the clauses
$(x_{(v,u)}\vee x_{(u,w)})$ and $(x_{(w,u)}\vee x_{(u,v)})$ to $\varphi$;

21 foreach  _$z\in N_{\overline{G}}(u)\cap L(v)$_ do add the clauses
$(x_{(v,u)}\vee x_{(u,z)})$ and $(x_{(z,u)}\vee x_{(u,v)})$ to $\varphi$;

22

23 end if

24 foreach  _$w\in U(u)\cap N_{\overline{G}}(v)$ with $vw\in E_{o}$_ do add
the clause $(x_{(w,v)}\vee x_{(v,u)})$ to $\varphi$ ;

25 foreach  _$z\in N_{\overline{G}}(u)\cap U(v)$ with $uz\in E_{o}$_ do add
the clause $(x_{(z,u)}\vee x_{(u,v)})$ to $\varphi$ ;

26

27 end foreach

28find a satisfying truth assignment $\tau$ of $\varphi$;

29 orient each edge $uv\in E_{o}$ as $(u,v)\in F$ if $x_{(u,v)}=0$ in $\tau$;

30 return _$F$_ ;

Algorithm 2 Algorithm for Lemma 10

The clauses added in lines 3–10 ensure that for any $C_{4}=(x,y,z,w)$ of
$\overline{G}$, either $(x,y),(z,y),(z,w),(x,w)\in F$ or
$(y,x),(y,z),(w,z),(w,x)\in F$. Similarly, the clauses added in lines 11–18
ensure that for any $K_{1,3}$ of $\overline{G}$ consisting of $x,y,z,w\in V$
with $xw,yw,zw\in E(\overline{G})$, either $(x,w),(y,w),(z,w)\in F$ or
$(w,x),(w,y),(w,z)\in F$. Moreover, the clauses added in lines 19 and 20
ensure that $P+F$ contains no forbidden configurations for $\mathbf{2+1}$.
Therefore, we have from Propositions 11 and 12 that $P+F$ contains no
forbidden configurations for $\mathbf{2+2}$, $\mathbf{3+1}$, or
$\mathbf{2+1}$.

Each iteration on lines 2–21 takes $O(n)$ time for each edge of $E_{o}$, and
hence $\varphi$ can be constructed in $O(n\bar{m})$ time. The 2-CNF formula
$\varphi$ has at most $n(n-1)/2$ Boolean variables and $O(n\bar{m})$ clauses.
Since a satisfying truth assignment of $\varphi$ can be obtained in time
linear to the size of $\varphi$ [1], Algorithm 2 takes $O(n\bar{m})$ time. ∎

We call a sequence of vertices $(v_{0},v_{1},v_{2},v_{3},v_{4},v_{5})$ a
_regular obstruction_ of $P+F$ if
$(v_{0},v_{1}),(v_{2},v_{3}),(v_{4},v_{5})\in P$ and
$(v_{2},v_{1}),(v_{4},v_{3}),(v_{0},v_{5})\in F$ (Fig. 44(a)). We call
$(v_{0},v_{1},v_{2},v_{3},v_{4},v_{5})$ a _skewed obstruction_ of $P+F$ if
$(v_{0},v_{1}),(v_{1},v_{2}),(v_{4},v_{5})\in P$ and
$(v_{3},v_{2}),(v_{4},v_{3}),(v_{0},v_{5}),(v_{5},v_{3})\in F$ (Fig. 44(b)).

$v_{0}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$ (a)
$v_{0}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$ (b)

Figure 4.  (a) A regular obstruction. (b) A skewed obstruction. An arrow $u\to
v$ denotes edge $(u,v)\in P$, and a dashed arrow $u\dasharrow v$ denotes edge
$(u,v)\in F$.

######  Lemma 13.

Let $F$ be an orientation of $E_{o}$ such that $P+F$ contains no forbidden
configurations for $\mathbf{2+2}$, $\mathbf{3+1}$, or $\mathbf{2+1}$. The
orientation $P+F$ is acyclic if and only if $P+F$ contains no obstructions.

Before proving Lemma 13, we introduce some observations.

######  Proposition 14.

Let $F$ be an orientation of $E_{o}$ such that $P+F$ contains no forbidden
configurations for $\mathbf{2+2}$ or $\mathbf{2+1}$. Let
$(v_{0},v_{1},v_{2},v_{3},v_{4},v_{5})$ be a regular obstruction of $P+F$. All
vertices of the obstruction are distinct. We have
$(v_{5},v_{2}),(v_{5},v_{3}),(v_{4},v_{2}),(v_{1},v_{4}),(v_{1},v_{5}),(v_{0},v_{4}),(v_{3},v_{0}),(v_{3},v_{1}),(v_{2},v_{1})\in
F$ (Fig. 44(a)).

###### Proof.

We have $v_{i}\neq v_{i+1}$ for any $i=0,1,\ldots,k-1$ (indices are modulo
$k$) since the graphs $G$ and $\overline{G}$ have no loops. We have $v_{i}\neq
v_{i+2}$ for any $i=0,1,\ldots,k-1$ since $(v_{i},v_{i+1})\in P$ and
$(v_{i+2},v_{i+1})\in F$ if $i$ is even, and $(v_{i+1},v_{i})\in F$ and
$(v_{i+1},v_{i+2})\in P$ if $i$ is odd. If $v_{0}=v_{3}$ then
$(v_{2},v_{3}),(v_{0},v_{1})\in P$ implies $(v_{2},v_{1})\in P$, contradicting
$(v_{2},v_{1})\in F$. Thus $v_{0}\neq v_{3}$. Similarly, we have $v_{1}\neq
v_{4}$ and $v_{2}\neq v_{5}$. Therefore, all vertices are distinct.

If $(v_{2},v_{5})\in P$ then $(v_{2},v_{5},v_{0},v_{1})$ is a forbidden
configuration for $\mathbf{2+2}$, a contradiction. If $(v_{5},v_{2})\in P$
then $(v_{4},v_{5}),(v_{2},v_{3})\in P$ implies $(v_{4},v_{3})\in P$,
contradicting $(v_{4},v_{3})\in F$. Thus $v_{2}v_{5}\in E(\overline{G})$.
Proposition 8 implies that $(v_{2},v_{4},v_{3},v_{5})$ is $C_{4}$ in
$\overline{G}$. Since $(v_{4},v_{3})\in F$, Proposition 11 implies
$(v_{5},v_{2}),(v_{5},v_{3}),(v_{4},v_{2})\in F$. By similar arguments, we
have $(v_{1},v_{4}),(v_{1},v_{5}),(v_{0},v_{4})\in F$ and
$(v_{3},v_{0}),(v_{3},v_{1}),(v_{2},v_{0})\in F$. ∎

######  Proposition 15.

Let $F$ be an orientation of $E_{o}$ such that $P+F$ contains no forbidden
configurations for $\mathbf{2+2}$, $\mathbf{3+1}$, or $\mathbf{2+1}$. Let
$(v_{0},v_{1},v_{2},v_{3},v_{4},v_{5})$ be a skewed obstruction of $P+F$. All
vertices of the obstruction are distinct. We have $(v_{0},v_{2})\in P$ and
$(v_{2},v_{5}),(v_{1},v_{4}),(v_{1},v_{5}),(v_{0},v_{4}),(v_{3},v_{0}),(v_{3},v_{1})\in
F$ (Fig. 44(b)).

###### Proof.

We have $v_{i}\neq v_{i+1}$ for any $i=0,1,\ldots,k-1$ (indices are modulo
$k$) since the graphs $G$ and $\overline{G}$ have no loops. We have $v_{0}\neq
v_{2}$ from $(v_{0},v_{1}),(v_{1},v_{2})\in P$. We have $v_{1}\neq v_{3}$ from
$(v_{1},v_{2})\in P$ and $(v_{3},v_{2})\in F$. We have $v_{2}\neq v_{4}$ from
$(v_{3},v_{2}),(v_{4},v_{3})\in F$. We have $v_{3}\neq v_{5}$ from
$(v_{4},v_{3})\in F$ and $(v_{4},v_{5})\in P$. We have $v_{4}\neq v_{0}$ from
$(v_{4},v_{5})\in P$ and $(v_{0},v_{5})\in F$. We have $v_{5}\neq v_{1}$ from
$(v_{0},v_{5})\in F$ and $(v_{0},v_{1})\in P$. If $v_{0}=v_{3}$ then
$(v_{0},v_{1}),(v_{1},v_{2})\in P$ implies $(v_{0},v_{2})\in P$, contradicting
$(v_{3},v_{2})\in F$. Thus $v_{0}\neq v_{3}$. If $v_{1}=v_{4}$ then
$(v_{0},v_{1}),(v_{4},v_{5})\in P$ implies $(v_{0},v_{5})\in P$, contradicting
$(v_{0},v_{5})\in F$. Thus $v_{1}\neq v_{4}$. If $v_{2}=v_{5}$ then
$(v_{0},v_{1}),(v_{1},v_{2})\in P$ implies $(v_{0},v_{2})\in P$, contradicting
$(v_{0},v_{5})\in F$. Thus $v_{2}\neq v_{5}$. Therefore, all vertices are
distinct.

We have $(v_{0},v_{2})\in P$ from $(v_{0},v_{1}),(v_{1},v_{2})\in P$. If
$(v_{2},v_{5})\in P$ then $(v_{0},v_{2})\in P$ implies $(v_{0},v_{5})\in P$,
contradicting $(v_{0},v_{5})\in F$. If $(v_{5},v_{2})\in P$ then
$(v_{4},v_{5},v_{2},v_{3})$ is a forbidden configuration for $\mathbf{3+1}$, a
contradiction. Thus $v_{2}v_{5}\in E(\overline{G})$. Proposition 9 implies
that the vertices $v_{0},v_{1},v_{2},v_{5}$ induce $K_{1,3}$ in
$\overline{G}$. Since $(v_{0},v_{5})\in F$, Proposition 12 implies
$(v_{2},v_{5}),(v_{1},v_{5})\in F$.

If $(v_{1},v_{4})\in P$ then $(v_{0},v_{1}),(v_{4},v_{5})\in P$ implies
$(v_{0},v_{5})\in P$, contradicting $(v_{0},v_{5})\in F$. If $(v_{4},v_{1})\in
P$ then $(v_{4},v_{1},v_{2},v_{3})$ is a forbidden configuration for
$\mathbf{3+1}$, a contradiction. Thus $v_{1}v_{4}\in E(\overline{G})$.
Proposition 8 implies that $(v_{0},v_{4},v_{1},v_{5})$ is $C_{4}$ in
$\overline{G}$. Since $(v_{0},v_{5})\in F$, Proposition 11 implies
$(v_{0},v_{4}),(v_{1},v_{5}),(v_{1},v_{4})\in F$.

If $(v_{0},v_{3})\in P$ then $(v_{0},v_{3},v_{4},v_{5})$ is a forbidden
configuration for $\mathbf{2+2}$, a contradiction. If $(v_{3},v_{0})\in P$
then $(v_{0},v_{2})\in P$ implies $(v_{3},v_{2})\in P$, contradicting
$(v_{3},v_{2})\in F$. Thus $v_{0}v_{3}\in E(\overline{G})$. Proposition 9
implies that the vertices $v_{0},v_{1},v_{2},v_{3}$ induce $K_{1,3}$ in
$\overline{G}$. Since $(v_{3},v_{2})\in F$, Proposition 12 implies
$(v_{3},v_{0}),(v_{3},v_{1})\in F$. ∎

A sequence of vertices $(a_{0},b_{0},a_{1},b_{1},\ldots,a_{k-1},b_{k-1})$ with
$k\geq 2$ is an _alternating cycle of length $2k$_ if $(a_{i},b_{i})\in P$ and
$(b_{i},a_{i+1})\in F$ for any $i=0,1,\ldots,k-1$ (indices are modulo $k$).
See Fig. 5 for example.

$a_{0}$$b_{0}$$a_{1}$$b_{1}$ (a) $a_{2}$$b_{1}$$a_{1}$$b_{0}$$a_{0}$$b_{2}$
(b) $a_{3}$$b_{3}$$a_{2}$$b_{2}$$a_{1}$$b_{1}$$a_{0}$$b_{0}$ (c)

Figure 5.  (a) An alternating cycle of length 4. (b) An alternating cycle of
length 6. (c) An alternating cycle of length greater than 6. Arrows and dashed
arrows denote the same type of edges as in Fig. 4. Dashed lines denote edges
of $\overline{G}$.

######  Proposition 16.

Let $F$ be an orientation of $E_{o}$ such that $P+F$ contains no forbidden
configurations for $\mathbf{2+1}$. The orientation $P+F$ contains no
alternating cycles of length 4.

###### Proof.

Suppose that $P+F$ contains an alternating cycle $(a_{0},b_{0},a_{1},b_{1})$
of length 4 (Fig. 55(a)). Proposition 8 implies that
$(a_{0},a_{1},b_{1},b_{0})$ is $C_{4}$, and hence $a_{0}a_{1}\in E_{o}$. If
$(a_{0},a_{1})\in F$ then $(a_{1},b_{1},a_{0})$ is a forbidden configuration
for $\mathbf{2+1}$, a contradiction. If $(a_{1},a_{0})\in F$ then
$(a_{0},b_{0},a_{1})$ is a forbidden configuration for $\mathbf{2+1}$, a
contradiction. ∎

Now, we prove Lemma 13.

###### Proof of Lemma 13.

We have from Propositions 14 and 15 that if $P+F$ contains an obstruction,
then $P+F$ contains a cycle. Now, we suppose that $P+F$ contains a cycle but
no obstructions.

######  Claim 8.

If $P+F$ contains an alternating cycle of length 6, then $P+F$ contains a
regular obstruction.

###### Proof of Claim 8.

Let $(a_{0},b_{0},a_{1},b_{1},a_{2},b_{3})$ be an alternating cycle of length
6 with $(a_{i},b_{i})\in P$ and $(b_{i},a_{i+1})\in F$ for any $i=0,1,2$
(indices are modulo 3). See Fig. 55(b). We first claim that the vertices are
distinct. We have $a_{i}\neq b_{i}$ and $b_{i}\neq a_{i+1}$ for any $i=0,1,2$
(indices are modulo 3) since the graphs $G$ and $\overline{G}$ have no loops.
We have $a_{i}\neq a_{i+1}$ for any $i=0,1,2$ since $(a_{i},b_{i})\in P$ and
$(b_{i},a_{i+1})\in F$. We also have $b_{i}\neq b_{i+1}$ for any $i=0,1,2$
since $(b_{i},a_{i+1})\in F$ and $(a_{i+1},b_{i+1})\in P$. If $a_{0}=b_{1}$
then $(a_{1},b_{1}),(a_{0},b_{0})\in P$ implies $(a_{1},b_{0})\in P$,
contradicting $(b_{0},a_{1})\in F$. Thus $a_{0}\neq b_{1}$. Similarly, we have
$a_{1}\neq b_{2}$ and $a_{2}\neq b_{0}$. Therefore, all vertices are distinct.

If $(a_{1},b_{2})\in P$ then $(a_{1},b_{2},a_{0},b_{0})$ is an alternating
cycle of length 4, contradicting Proposition 16. If $(b_{2},a_{1})\in P$ then
$(a_{2},b_{2}),(a_{1},b_{1})\in P$ implies $(a_{2},b_{1})\in P$, contradicting
$(b_{1},a_{2})\in F$. Thus $a_{1}b_{2}\in E(\overline{G})$. Proposition 8
implies that $(a_{1},a_{2},b_{1},b_{2})$ is $C_{4}$ in $\overline{G}$. Since
$(b_{1},a_{2})\in F$, Proposition 11 implies $(a_{1},b_{2})\in F$. By similar
arguments, we have $(a_{0},b_{1}),(a_{2},b_{0})\in F$. Now,
$(a_{0},b_{0},a_{2},b_{2},a_{1},b_{1})$ is a regular obstruction. ∎

######  Claim 9.

If $P+F$ contains an alternating cycle of length greater than 6, then $P+F$
contains an alternating cycle of length 6.

###### Proof of Claim 9.

Suppose that $P+F$ contains no alternating cycles of length 6. We show that
$P+F$ contains no alternating cycles of length greater than 6. Suppose to the
contrary that $P+F$ contains an alternating cycle
$(a_{0},b_{0},a_{1},b_{1},\ldots,a_{k-1},b_{k-1})$ of length $2k$ with $k\geq
4$ (Fig. 55(c)). Assume without loss of generality that the length of the
cycle is minimal.

If $a_{0}=b_{2}$ then $(a_{2},b_{2}),(a_{0},b_{0})\in P$ implies
$(a_{2},b_{0})\in P$, and hence $(a_{2},b_{0},a_{1},b_{1})$ is an alternating
cycle of length 4, contradicting Proposition 16. If $(a_{0},b_{2})\in P$ then
$(a_{0},b_{2},a_{3},b_{3},\ldots,a_{k-1},b_{k-1})$ is an alternating cycle of
length $2(k-2)$, contradicting the minimality of the length of the cycle. If
$(b_{2},a_{0})\in P$ then $(a_{2},b_{2}),(a_{0},b_{0})\in P$ implies
$(a_{2},b_{0})\in P$, and hence $(a_{2},b_{0},a_{1},b_{1})$ is an alternating
cycle of length 4, contradicting Proposition 16. Therefore, $a_{0}b_{2}\in
E(\overline{G})$.

If $b_{0}=a_{2}$ then $(a_{0},b_{0}),(a_{2},b_{2})\in P$ implies
$(a_{0},b_{2})\in P$, contradicting $a_{0}b_{2}\in E(\overline{G})$. If
$(a_{2},b_{0})\in P$ then $(a_{2},b_{0},a_{1},b_{1})$ is an alternating cycle
of length 4, contradicting Proposition 16. If $(b_{0},a_{2})\in P$ then
$(a_{0},b_{0}),(a_{2},b_{2})\in P$ implies $(a_{0},b_{2})\in P$, contradicting
$a_{0}b_{2}\in E(\overline{G})$. Therefore, $b_{0}a_{2}\in E(\overline{G})$.

Now, Proposition 8 implies that $(a_{0},a_{2},b_{0},b_{2})$ is $C_{4}$. If
$(a_{0},b_{2}),(b_{0},a_{2})\in F$ then
$(a_{0},b_{0},a_{2},b_{2},a_{3},b_{3},\ldots,a_{k-1},b_{k-1})$ is an
alternating cycle of length $2(k-1)$, a contradiction. If
$(b_{2},a_{0}),(a_{2},b_{0})\in F$ then
$(a_{0},b_{0},a_{1},b_{1},a_{2},b_{2})$ is an alternating cycle of length 6, a
contradiction. Thus $P+F$ contains no alternating cycles of length greater
than 6. ∎

Therefore, we can assume that $P+F$ contains no alternating cycles.

We now introduce some definitions. We call an edge $(x,y)\in F$ _type-1
critical_ if there is $\mathbf{3+1}$ consisting of four vertices $x$, $y$,
$z$, $w$ with $(y,z),(z,w)\in P$ and $(x,y),(x,z),(x,w)\in F$ (Fig. 66(a)). We
call an edge $(x,y)\in F$ _type-2 critical_ if there is $\mathbf{2+2}$
consisting of four vertices $x$, $y$, $z$, $w$ with $(w,x),(y,z)\in P$ and
$(x,y),(x,z),(w,y),(w,z)\in F$ (Fig. 66(b)). We call an edge $(x,y)\in F$
_type-3 critical_ if there is $\mathbf{3+1}$ consisting of four vertices $x$,
$y$, $z$, $w$ with $(z,w),(w,x)\in P$ and $(x,y),(w,y),(z,y)\in F$ (Fig.
66(c)).

$x$$y$$z$$w$ (a) $x$$y$$z$$w$ (b) $x$$y$$z$$w$ (c)

Figure 6.  (a) A type-1 critical edge $(x,y)$. (b) A type-2 critical edge
$(x,y)$. (c) A type-3 critical edge $(x,y)$. Arrows and dashed arrows denote
the same type of edges as in Fig. 5.

For any edge $(u,v)\in F$, there is a directed path from $u$ to $v$ consisting
of a critical edge and edges in $P$. For example, in Fig. 66(a), there is a
path $(x,y,w)$ for $(x,w)\in F$. Recall that $P+F$ contains a cycle.
Therefore, $P+F$ contains a cycle consisting of critical edges and edges in
$P$.

Let $C$ be a shortest cycle consisting of critical edges and edges in $P$. If
there are three vertices $u,v,w$ consecutive on $C$ with $(u,v),(v,w)\in P$,
then $(u,w)\in P$. Hence we have a shorter cycle consisting of critical edges
and edges in $P$, contradicting the minimality of length of $C$. Thus there
are no three vertices $u,v,w$ consecutive on $C$ with $(u,v),(v,w)\in P$.

Recall that $P+F$ contains no alternating cycles. Therefore, there are three
vertices $u,v,w$ consecutive on $C$ with $(u,v),(v,w)\in F$. If $(u,w)\in P$
or $(w,u)\in P$, then we have a shorter cycle consisting of critical edges and
edges in $P$, a contradiction. Thus $uw\in E(\overline{G})$. If $(u,w)\in F$
and $(u,w)$ is a critical edge, then we have a shorter cycle consisting of
critical edges and edges in $P$, a contradiction. Thus we have the following.

######  Claim 10.

If $(u,w)\in F$ then $(u,w)$ is not a critical edge.

We distinguish nine cases (Fig. 7). Case 1-1: $(u,v)$ is type-1 critical and
$(v,w)$ is type-1 critical; Case 1-2: $(u,v)$ is type-1 critical and $(v,w)$
is type-2 critical; Case 1-3: $(u,v)$ is type-1 critical and $(v,w)$ is type-3
critical; Case 2-1: $(u,v)$ is type-2 critical and $(v,w)$ is type-1 critical;
Case 2-2: $(u,v)$ is type-2 critical and $(v,w)$ is type-2 critical; Case 2-3:
$(u,v)$ is type-2 critical and $(v,w)$ is type-3 critical; Case 3-1: $(u,v)$
is type-3 critical and $(v,w)$ is type-1 critical; Case 3-2: $(u,v)$ is type-3
critical and $(v,w)$ is type-2 critical; Case 3-3: $(u,v)$ is type-3 critical
and $(v,w)$ is type-3 critical.

$u$$v$$w$$a$$b$$c$$d$ (a) Case 1-1 $u$$v$$w$$a$$b$$c$$d$ (b) Case 1-2
$u$$v$$w$$a$$b$$c$$d$ (c) Case 1-3

$u$$v$$w$$a$$b$$c$$d$ (d) Case 2-1 $u$$v$$w$$a$$b$$c$$d$ (e) Case 2-2
$u$$v$$w$$a$$b$$c$$d$ (f) Case 2-3

$u$$v$$w$$a$$b$$c$$d$ (g) Case 3-1 $u$$v$$w$$a$$b$$c$$d$ (h) Case 3-2
$u$$v$$w$$a$$b$$c$$d$ (i) Case 3-3

Figure 7.  Illustrating the proof of Claims 11 and 12. Arrows, dashed arrows,
and dashed lines denote the same type of edges as in Fig. 5.

######  Claim 11.

In Cases 2-1, 2-2, and 3-2, the orientation $P+F$ contains a regular
obstruction. In Cases 1-1, 3-1, and 3-3, the orientation $P+F$ contains a
skewed obstruction.

###### Proof of Claim 11.

We prove the claim for each case.

_Case 1-1_ (Fig. 77(a)). Since $(u,v)$ is type-1 critical, there are two other
vertices $a,b$ with $(v,b),(b,a)\in P$ and $(u,a)\in F$. Note that
$(v,b),(b,a)\in P$ implies $(v,a)\in P$. We have $a\neq w$ from $(v,a)\in P$
and $(v,w)\in F$. We also have $b\neq w$ from $(v,b)\in P$ and $(v,w)\in F$.
Therefore, the five vertices $u,v,w,a,b$ are distinct.

Since $(v,w)$ is type-1 critical, there are two other vertices $c,d$ with
$(w,d),(d,c)\in P$ and $(v,c)\in F$. Note that $(w,d),(d,c)\in P$ implies
$(w,c)\in P$. We have $c\neq u$ from $(v,c),(u,v)\in F$. We also have $c\neq
b$ from $(v,c)\in F$ and $(v,b)\in P$. Moreover, we have $c\neq a$ from
$(v,c)\in F$ and $(v,a)\in P$. Therefore, the six vertices $u,v,w,a,b,c$ are
distinct. We have $d\neq u$ from $(w,d)\in P$ and $uw\in E(\overline{G})$. If
$d=b$ then $(v,b),(d,c)\in P$ implies $(v,c)\in P$, contradicting $(v,c)\in
F$. Thus $d\neq b$. Similarly, if $d=a$ then $(v,a),(d,c)\in P$ implies
$(v,c)\in P$, contradicting $(v,c)\in F$. Thus $d\neq a$. Therefore, the seven
vertices $u,v,w,a,b,c,d$ are distinct.

If $(c,u)\in P$ then $(w,c)\in P$ implies $(w,u)\in P$, contradicting $uw\in
E(\overline{G})$. If $(u,c)\in P$ then $(u,c,v,a)$ is a forbidden
configuration for $\mathbf{2+2}$, a contradiction. Thus $uc\in
E(\overline{G})$. Proposition 9 implies that the vertices $w,d,c,u$ induce
$K_{1,3}$ in $\overline{G}$. If $(u,w)\in F$ then $(u,w)$ is type-1 critical,
contradicting Claim 10. Thus $(w,u)\in F$, and then $(v,b,a,u,w,c)$ is a
skewed obstruction.

_Case 2-1_ (Fig. 77(d)). Since $(u,v)$ is type-2 critical, there are two other
vertices $a,b$ with $(a,u),(v,b)\in P$ and $(a,b)\in F$. We have $a\neq w$
from $(a,u)\in P$ and $uw\in E(\overline{G})$. We also have $b\neq w$ from
$(v,b)\in P$ and $(v,w)\in F$. Therefore, the five vertices $u,v,w,a,b$ are
distinct.

Since $(v,w)$ is type-1 critical, there are two other vertices $c,d$ with
$(w,d),(d,c)\in P$ and $(v,c)\in F$. Note that $(w,d),(d,c)\in P$ implies
$(w,c)\in P$. We have $c\neq u$ from $(v,c),(u,v)\in F$. We also have $c\neq
b$ from $(v,c)\in F$ and $(v,b)\in P$. If $c=a$ then $(w,c),(a,u)\in P$
implies $(w,u)\in P$, contradicting $uw\in E(\overline{G})$. Thus $c\neq a$.
Therefore, the six vertices $u,v,w,a,b,c$ are distinct. We have $d\neq u$ from
$(w,d)\in P$ and $uw\in E(\overline{G})$. If $d=b$ then $(v,b),(d,c)\in P$
implies $(v,c)\in P$, contradicting $(v,c)\in F$. Thus $d\neq b$. If $d=a$
then $(w,d),(a,u)\in P$ implies $(w,u)\in P$, contradicting $uw\in
E(\overline{G})$. Thus $d\neq a$. Therefore, the seven vertices
$u,v,w,a,b,c,d$ are distinct.

If $(c,a)\in P$ then $(w,c),(a,u)\in P$ implies $(w,u)\in P$, contradicting
$uw\in E(\overline{G})$. If $(a,c)\in P$ then $(a,c,v,b)$ is a forbidden
configuration for $\mathbf{2+2}$, a contradiction. Thus $ac\in
E(\overline{G})$. Proposition 8 implies that $(a,w,u,c)$ is $C_{4}$ in
$\overline{G}$. If $(u,w)\in F$ then $(u,w)$ is type-2 critical, contradicting
Claim 10. Thus $(w,u)\in F$, and then $(a,u,w,c,v,b)$ is a regular
obstruction.

_Case 2-2_ (Fig. 77(e)). As in Case 2-1, there are two vertices $a,b$ with
$(a,u),(v,b)\in P$ and $(a,b)\in F$, and the five vertices $u,v,w,a,b$ are
distinct. Since $(v,w)$ is type-2 critical, there are two other vertices $c,d$
with $(c,v),(w,d)\in P$ and $(c,d)\in F$. We have $c\neq u$ from $(c,v)\in P$
and $(u,v)\in F$. We also have $c\neq b$ from $(c,v),(v,b)\in P$. Thus we have
$(c,b)\in P$ from $(c,v),(v,b)\in P$. We have $c\neq a$ from $(c,b)\in P$ and
$(a,b)\in F$. Therefore, the six vertices $u,v,w,a,b,c$ are distinct. We have
$d\neq u$ from $(w,d)\in P$ and $uw\in E(\overline{G})$. We also have $d\neq
b$ from $(c,d)\in F$ and $(c,b)\in P$. If $d=a$ then $(w,d),(a,u)\in P$
implies $(w,u)\in P$, contradicting $uw\in E(\overline{G})$. Thus $d\neq a$.
Therefore, the seven vertices $u,v,w,a,b,c,d$ are distinct.

If $(d,a)\in P$ then $(w,d),(a,u)\in P$ implies $(w,u)\in P$, contradicting
$uw\in E(\overline{G})$. If $(a,d)\in P$ then $(a,d,c,b)$ is a forbidden
configuration for $\mathbf{2+2}$, a contradiction. Thus $ad\in
E(\overline{G})$. Proposition 8 implies that $(a,w,u,d)$ is $C_{4}$ in
$\overline{G}$. If $(u,w)\in F$ then $(u,w)$ is type-2 critical, contradicting
Claim 10. Thus $(w,u)\in F$, and then $(a,u,w,d,c,b)$ is a regular
obstruction.

_Case 3-1_ (Fig. 77(g)). Since $(u,v)$ is type-3 critical, there are two other
vertices $a,b$ with $(b,a),(a,u)\in P$ and $(b,v)\in F$. Note that
$(b,a),(a,u)\in P$ implies $(b,u)\in P$. We have $a\neq w$ from $(a,u)\in P$
and $uw\in E(\overline{G})$. We also have $b\neq w$ from $(b,v),(v,w)\in F$.
Therefore, the five vertices $u,v,w,a,b$ are distinct.

Since $(v,w)$ is type-1 critical, there are two other vertices $c,d$ with
$(w,d),(d,c)\in P$ and $(v,c)\in F$. We have $c\neq u$ from $(v,c),(u,v)\in
F$. We also have $c\neq b$ from $(v,c),(b,v)\in F$. If $c=a$ then
$(w,d),(d,c),(a,u)\in P$ implies $(w,u)\in P$, contradicting $uw\in
E(\overline{G})$. Thus $c\neq a$. Therefore, the six vertices $u,v,w,a,b,c$
are distinct. We have $d\neq u$ from $(w,d)\in P$ and $uw\in E(\overline{G})$.
If $d=b$ then $(w,d),(b,u)\in P$ implies $(w,u)\in P$, contradicting $uw\in
E(\overline{G})$. Thus $d\neq b$. Similarly, if $d=a$ then $(w,d),(a,u)\in P$
implies $(w,u)\in P$, contradicting $uw\in E(\overline{G})$. Thus $d\neq a$.
Therefore, the seven vertices $u,v,w,a,b,c,d$ are distinct.

If $(d,b)\in P$ then $(w,d),(b,u)\in P$ implies $(w,u)\in P$, contradicting
$uw\in E(\overline{G})$. If $(b,d)\in P$ then $(b,d,c,v)$ is a forbidden
configuration for $\mathbf{3+1}$, a contradiction. Thus $bd\in
E(\overline{G})$. Proposition 8 implies that $(b,w,u,d)$ is $C_{4}$ in
$\overline{G}$. If $(u,w)\in F$ then $(u,w)$ is type-2 critical, contradicting
Claim 10. Thus $(w,u)\in F$, and then $(w,d,c,v,b,u)$ is a skewed obstruction.

_Case 3-2_ (Fig. 77(h)). As in Case 3-1, there are two vertices $a,b$ with
$(b,a),(a,u)\in P$ and $(b,v)\in F$, and the five vertices $u,v,w,a,b$ are
distinct. Note that $(b,a),(a,u)\in P$ implies $(b,u)\in P$. Since $(v,w)$ is
type-2 critical, there are two other vertices $c,d$ with $(c,v),(w,d)\in P$
and $(c,d)\in F$. We have $c\neq u$ from $(c,v)\in P$ and $(u,v)\in F$. We
also have $c\neq b$ from $(c,v)\in P$ and $(b,v)\in F$. If $c=a$ then
$(b,a),(c,v)\in P$ implies $(b,v)\in P$, contradicting $(b,v)\in F$. Thus
$c\neq a$. Therefore, the six vertices $u,v,w,a,b,c$ are distinct. We have
$d\neq u$ from $(w,d)\in P$ and $uw\in E(\overline{G})$. If $d=b$ then
$(w,d),(b,u)\in P$ implies $(w,u)\in P$, contradicting $uw\in
E(\overline{G})$. Thus $d\neq b$. Similarly, if $d=a$ then $(w,d),(a,u)\in P$
implies $(w,u)\in P$, contradicting $uw\in E(\overline{G})$. Thus $d\neq a$.
Therefore, the seven vertices $u,v,w,a,b,c,d$ are distinct.

If $(d,b)\in P$ then $(w,d),(b,u)\in P$ implies $(w,u)\in P$, contradicting
$uw\in E(\overline{G})$. If $(b,d)\in P$ then $(b,d,c,v)$ is a forbidden
configuration for $\mathbf{2+2}$, a contradiction. Thus $bd\in
E(\overline{G})$. Proposition 8 implies that $(b,w,u,d)$ is $C_{4}$ in
$\overline{G}$. If $(u,w)\in F$ then $(u,w)$ is type-2 critical, contradicting
Claim 10. Thus $(w,u)\in F$, and then $(b,u,w,d,c,v)$ is a regular
obstruction.

_Case 3-3_ (Fig. 77(i)). As in Case 3-1, there are two vertices $a,b$ with
$(b,a),(a,u)\in P$ and $(b,v)\in F$, and the five vertices $u,v,w,a,b$ are
distinct. Since $(v,w)$ is type-3 critical, there are two other vertices $c,d$
with $(d,c),(c,v)\in P$ and $(d,w)\in F$. Note that $(d,c),(c,v)\in P$ implies
$(d,v)\in P$. We have $c\neq u$ from $(c,v)\in P$ and $(u,v)\in F$. We also
have $c\neq b$ from $(c,v)\in P$ and $(b,v)\in F$. If $c=a$ then
$(b,a),(c,v)\in P$ implies $(b,v)\in P$, contradicting $(b,v)\in F$. Thus
$c\neq a$. Therefore, the six vertices $u,v,w,a,b,c$ are distinct. We have
$d\neq u$ from $(d,v)\in P$ and $(u,v)\in F$. We also have $d\neq b$ from
$(d,v)\in P$ and $(b,v)\in F$. If $d=a$ then $(b,a),(d,v)\in P$ implies
$(b,v)\in P$, contradicting $(b,v)\in F$. Thus $d\neq a$. Therefore, the seven
vertices $u,v,w,a,b,c,d$ are distinct.

If $(w,b)\in P$ then $(b,a),(a,u)\in P$ implies $(w,u)\in P$, contradicting
$uw\in E(\overline{G})$. If $(b,w)\in P$ then $(b,w,d,v)$ is a forbidden
configuration for $\mathbf{2+2}$, a contradiction. Thus $bw\in
E(\overline{G})$. Proposition 9 implies that the vertices $b,a,u,w$ induce
$K_{1,3}$ in $\overline{G}$. If $(u,w)\in F$ then $(u,w)$ is type-3 critical,
contradicting Claim 10. Thus $(w,u)\in F$, and then $(b,a,u,w,d,v)$ is a
skewed obstruction. ∎

######  Claim 12.

In Cases 1-2, 1-3, and 2-3, there is a sequence of vertices $(u,x,y,w)$ such
that

  1. –

$(u,x),(y,w)\in F$ and $(x,y)\in P$;

  2. –

$(u,x)$ is a critical edge with the same type of $(u,v)$;

  3. –

$(y,w)$ is a critical edge with the same type of $(v,w)$.

###### Proof of Claim 12.

We prove the claim for each case.

_Case 1-2_ (Fig. 77(b)). As in Case 1-1, there are two vertices $a,b$ with
$(v,b),(b,a)\in P$ and $(u,a)\in F$, and the five vertices $u,v,w,a,b$ are
distinct. Since $(v,w)$ is type-2 critical, there are two other vertices $c,d$
with $(c,v),(w,d)\in P$ and $(c,d)\in F$. We have $c\neq u$ from $(c,v)\in P$
and $(u,v)\in F$. We also have $c\neq b$ from $(c,v),(v,b)\in P$. Thus we have
$(c,b)\in P$ from $(c,v),(v,b)\in P$. We have $c\neq a$ from $(c,b),(b,a)\in
P$. Therefore, the six vertices $u,v,w,a,b,c$ are distinct. We have $d\neq u$
from $(w,d)\in P$ and $uw\in E(\overline{G})$. We also have $d\neq b$ from
$(c,d)\in F$ and $(c,b)\in P$. If $d=a$ then $(c,b),(b,a)\in P$ implies
$(c,a)\in P$, contradicting $(c,d)\in F$. Thus $d\neq a$. Therefore, the seven
vertices $u,v,w,a,b,c,d$ are distinct.

If $(u,c)\in P$ then $(c,v)\in P$ implies $(u,v)\in P$, contradicting
$(u,v)\in F$. Suppose $(c,u)\in P$. Proposition 8 implies that $(c,w,u,d)$ is
$C_{4}$ in $\overline{G}$. We have $(u,w)\in F$ from $(c,d)\in F$, but $(u,w)$
is type-2 critical, contradicting Claim 10. Thus $uc\in E(\overline{G})$. Then
Proposition 9 implies that the vertices $c,b,a,u$ induce $K_{1,3}$ in
$\overline{G}$. We have $(u,c)\in F$ from $(u,a)\in F$, and $(u,c)$ is type-1
critical. Therefore, $(u,c,v,w)$ is a desired sequence.

_Case 1-3_ (Fig. 77(c)). As in Case 1-1, there are two vertices $a,b$ with
$(v,b),(b,a)\in P$ and $(u,a)\in F$, and the five vertices $u,v,w,a,b$ are
distinct. Since $(v,w)$ is type-3 critical, there are two other vertices $c,d$
with $(d,c),(c,v)\in P$ and $(d,w)\in F$. Note that $(d,c),(c,v)\in P$ implies
$(d,v)\in P$. We have $c\neq u$ from $(c,v)\in P$ and $(u,v)\in F$. We also
have $c\neq b$ from $(c,v),(v,b)\in P$. Thus we have $(c,b)\in P$ from
$(c,v),(v,b)\in P$. We have $c\neq a$ from $(c,b),(b,a)\in P$. Therefore, the
six vertices $u,v,w,a,b,c$ are distinct. We have $d\neq u$ from $(d,v)\in P$
and $(u,v)\in F$. We also have $d\neq b$ from $(d,c),(c,b)\in P$. Moreover, we
have $d\neq a$ from $(d,c),(c,b),(b,a)\in P$. Therefore, the seven vertices
$u,v,w,a,b,c,d$ are distinct.

If $(u,c)\in P$ then $(c,v)\in P$ implies $(u,v)\in P$, contradicting
$(u,v)\in F$. Suppose $(c,u)\in P$. Proposition 9 implies that the vertices
$d,c,u,w$ induce $K_{1,3}$ in $\overline{G}$. We have $(u,w)\in F$ from
$(d,w)\in F$, but $(u,w)$ is type-3 critical, contradicting Claim 10. Thus
$uc\in E(\overline{G})$. Then Proposition 9 implies that the vertices
$c,b,a,u$ induce $K_{1,3}$ in $\overline{G}$. We have $(u,c)\in F$ from
$(u,a)\in F$, and $(u,c)$ is type-1 critical. Therefore, $(u,c,v,w)$ is a
desired sequence.

_Case 2-3_ (Fig. 77(f)). As in Case 2-1, there are two vertices $a,b$ with
$(a,u),(v,b)\in P$ and $(a,b)\in F$, and the five vertices $u,v,w,a,b$ are
distinct. Since $(v,w)$ is type-3 critical, there are two other vertices $c,d$
with $(d,c),(c,v)\in P$ and $(d,w)\in F$. Note that $(d,c),(c,v)\in P$ implies
$(d,v)\in P$. We have $c\neq u$ from $(c,v)\in P$ and $(u,v)\in F$. We also
have $c\neq b$ from $(c,v),(v,b)\in P$. Thus we have $(c,b)\in P$ from
$(c,v),(v,b)\in P$. We have $c\neq a$ from $(c,b)\in P$ and $(a,b)\in F$.
Therefore, the six vertices $u,v,w,a,b,c$ are distinct. We have $d\neq u$ from
$(d,v)\in P$ and $(u,v)\in F$. We also have $d\neq b$ from $(d,c),(c,b)\in P$.
If $d=a$ then $(d,c),(c,b)\in P$ implies $(d,b)\in P$, contradicting $(a,b)\in
F$. Thus $d\neq a$. Therefore, the seven vertices $u,v,w,a,b,c,d$ are
distinct.

If $(u,c)\in P$ then $(c,v)\in P$ implies $(u,v)\in P$, contradicting
$(u,v)\in F$. Suppose $(c,u)\in P$. We have from Proposition 9 that the
vertices $d,c,u,w$ induce $K_{1,3}$ in $\overline{G}$. We have $(u,w)\in F$
from $(d,w)\in F$, but $(u,w)$ is type-3 critical, contradicting Claim 10.
Thus $uc\in E(\overline{G})$. Then Proposition 8 implies that $(a,c,u,b)$ is
$C_{4}$ in $\overline{G}$. We have $(u,c)\in F$ from $(a,b)\in F$, and $(u,c)$
is type-2 critical. Therefore, $(u,c,v,w)$ is a desired sequence. ∎

By Claim 11, we can assume that any two critical edges consecutive on $C$ is
in Cases 1-2, 1-3, and 2-3. However, we can obtain an alternating cycle from
$C$ by repeated applications of Claim 12, a contradiction. Thus the lemma
holds. ∎

######  Lemma 17.

Let $F$ be an orientation of $E_{o}$ such that $P+F$ contains no forbidden
configurations for $\mathbf{2+2}$, $\mathbf{3+1}$, or $\mathbf{2+1}$. We can
compute in $O(m\bar{m}^{2})$ time an orientation $F^{\prime}$ of $E_{o}$ such
that $P+F^{\prime}$ contains no forbidden configurations for $\mathbf{2+2}$,
$\mathbf{3+1}$, or $\mathbf{2+1}$, and $P+F^{\prime}$ contains no
obstructions.

###### Proof.

Let $(v_{0},v_{1},v_{2},v_{3},v_{4},v_{5})$ be a regular obstruction. We call
the edge $(v_{0},v_{1})\in P$ the _base_ of the obstruction and the edges
$(v_{4},v_{3}),(v_{5},v_{3}),(v_{4},v_{2}),(v_{5},v_{2})\in F$ its _fronts_.
Similarly, let $(v_{0},v_{1},v_{2},v_{3},v_{4},v_{5})$ be a skewed
obstruction. We call the edge $(v_{0},v_{1})\in P$ the _base_ of the
obstruction and the edges $(v_{4},v_{3}),(v_{5},v_{3})\in F$ its _fronts_. We
can observe the following from Propositions 14 and 15 (Fig. 4).

######  Claim 13.

If $(u,v)\in P$ is the base of an obstruction and $(x,y)\in F$ is its front,
then $(u,x),(v,x),(y,u),(y,v)\in F$.

Let $F$ be an orientation of $E_{o}$ such that $P+F$ contains no forbidden
configurations for $\mathbf{2+2}$, $\mathbf{3+1}$, or $\mathbf{2+1}$. Then,
let $(u,v)$ be an edge in $P$. We define that

$\displaystyle A_{(u,v)}$ $\displaystyle=\\{(x,y)\in F\colon\ \text{there is a
regular obstruction such that $(u,v)$ is its base and $(x,y)$ is its
front}\\},$ $\displaystyle A_{(u,v)}^{-1}$ $\displaystyle=\\{(y,x)\colon\
(x,y)\in A_{(u,v)}\\},\text{ and }$ $\displaystyle F^{\prime}$
$\displaystyle=(F-A_{(u,v)})+A_{(u,v)}^{-1}.$

In other words, $F^{\prime}$ is an orientation of $E_{o}$ obtained from $F$ by
reversing the direction of all edges in $A_{(u,v)}$.

$u$$v$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$w$$x$ (a)
$u$$v$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$x$$y$ (b)
$u$$v$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$x$$y$ (c)

$u$$v$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$y$$z$ (d)
$u$$v$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$y$$z$ (e)
$u$$v$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$x$ (f)

$u$$v$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$x$ (g)
$u$$v$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$y$ (h)
$u$$v$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$y$ (i)

Figure 8.  Illustrating the proof of Claims 14–16. Arrows and dashed arrows
denote the same type of edges as in Fig. 5.

######  Claim 14.

The orientation $P+F^{\prime}$ contains no forbidden configurations for
$\mathbf{2+2}$.

###### Proof of Claim 14.

Suppose that $P+F^{\prime}$ contains a forbidden configuration $(x,y,z,w)$ for
$\mathbf{2+2}$. If $(z,y),(x,w)\in A_{(u,v)}^{-1}$ then $(y,z),(w,x)\in F$,
that is, $(x,y,z,w)$ is an alternating cycle of length 4 in $P+F$,
contradicting Proposition 16. Thus either $(z,y)\in A_{(u,v)}^{-1}$ or
$(x,w)\in A_{(u,v)}^{-1}$. Assume without loss of generality $(z,y)\in
A_{(u,v)}^{-1}$ and $(x,w)\notin A_{(u,v)}^{-1}$. Then $(y,z)\in
A_{(u,v)}\subseteq F$ and $(x,w)\in F$ but $(x,w)\notin A_{(u,v)}$.

Since $(y,z)\in A_{(u,v)}$, there is a regular obstruction
$(u,v,v_{2},v_{3},v_{4},v_{5})$ of $P+F$ such that $(u,v)$ is its base and
$(y,z)$ is its front. Suppose $(y,z)=(v_{4},v_{3})$ (Fig. 88(a)). We have
$(v_{2},w)\in P$ from $(v_{2},v_{3}),(v_{3},w)\in P$. We also have
$(x,v_{5})\in P$ from $(x,v_{4}),(v_{4},v_{5})\in P$. Then
$(u,v,v_{2},w,x,v_{5})$ is a regular obstruction, and hence $(x,w)\in
A_{(u,v)}$, a contradiction. Suppose $(y,z)=(v_{5},v_{3})$. We have
$(v_{2},w)\in P$ from $(v_{2},v_{3}),(v_{3},w)\in P$. Then
$(u,v,v_{2},w,x,v_{5})$ is a regular obstruction, and hence $(x,w)\in
A_{(u,v)}$, a contradiction. Suppose $(y,z)=(v_{4},v_{2})$. We have
$(x,v_{5})\in P$ from $(x,v_{4}),(v_{4},v_{5})\in P$. Then
$(u,v,v_{2},w,x,v_{5})$ is a regular obstruction, and hence $(x,w)\in
A_{(u,v)}$, a contradiction. Suppose $(y,z)=(v_{5},v_{3})$. Then
$(u,v,v_{2},w,x,v_{5})$ is a regular obstruction, and hence $(x,w)\in
A_{(u,v)}$, a contradiction. ∎

######  Claim 15.

The orientation $P+F^{\prime}$ contains no forbidden configurations for
$\mathbf{3+1}$.

###### Proof of Claim 15.

Suppose that $P+F^{\prime}$ contains a forbidden configuration $(x,y,z,w)$ for
$\mathbf{3+1}$. Note that $(x,y),(y,z)\in P$ implies $(x,z)\in P$. If
$(w,z),(x,w)\in A_{(u,v)}^{-1}$ then $(z,w),(w,x)\in F$, that is, $(x,z,w)$ is
a forbidden configuration for $\mathbf{2+1}$ in $P+F$, a contradiction. Thus
either $(w,z)\in A_{(u,v)}^{-1}$ or $(x,w)\in A_{(u,v)}^{-1}$.

We first suppose $(w,z)\in A_{(u,v)}^{-1}$ and $(x,w)\notin A_{(u,v)}^{-1}$.
We have $(z,w)\in A_{(u,v)}\subseteq F$ and $(x,w)\in F$ but $(x,w)\notin
A_{(u,v)}$. Since $(z,w)\in A_{(u,v)}$, there is a regular obstruction
$(u,v,v_{2},v_{3},v_{4},v_{5})$ of $P+F$ such that $(u,v)$ is its base and
$(z,w)$ is its front. Suppose $(z,w)=(v_{4},v_{3})$ (Fig. 88(b)). We have
$(x,v_{5})\in P$ from $(x,y),(y,v_{4}),(v_{4},v_{5})\in P$. Then
$(u,v,v_{2},v_{3},x,v_{5})$ is a regular obstruction, and hence $(x,v_{3})\in
A_{(u,v)}$, a contradiction. Suppose $(z,w)=(v_{5},v_{3})$. We have
$(x,v_{5})\in P$ from $(x,y),(y,v_{5})\in P$. Then $(u,v,v_{2},v_{3},x,v_{5})$
is a regular obstruction, and hence $(x,v_{3})\in A_{(u,v)}$, a contradiction.

Suppose $(z,w)=(v_{4},v_{2})$ (Fig. 88(c)). We have $(x,v_{5})\in P$ from
$(x,y),(y,v_{4}),(v_{4},v_{5})\in P$. We also have $(v_{5},v_{3}),(v_{3},u)\in
F$ from Proposition 14. If $(u,x)\in P$ then $(x,v_{5})\in P$ implies
$(u,v_{5})\in P$, contradicting $(u,v_{5})\in F$. If $(x,u)\in P$ then
$(x,u,v,v_{2})$ is a forbidden configuration for $\mathbf{3+1}$ in $P+F$, a
contradiction. Thus $ux\in E(\overline{G})$. Proposition 9 implies that the
vertices $x,y,v_{5},u$ induce $K_{1,3}$ in $\overline{G}$. Then we have
$(u,x)\in F$ from $(u,v_{5})\in F$. If $(x,v_{3})\in P$ then $(x,v_{3},u)$ is
a forbidden configuration for $\mathbf{2+1}$ in $P+F$, a contradiction. If
$(v_{3},x)\in P$ then $(v_{2},v_{3})\in P$ implies $(v_{2},x)\in P$,
contradicting $(x,v_{2})\in F$. Thus $v_{3}x\in E(\overline{G})$. Proposition
9 implies that the vertices $x,y,v_{5},v_{3}$ induce $K_{1,3}$ in
$\overline{G}$, and we have $(x,v_{3})\in F$ from $(v_{5},v_{3})\in F$. Then
$(u,v,v_{2},v_{3},x,v_{5})$ is a regular obstruction, and hence $(x,v_{2})\in
A_{(u,v)}$, a contradiction. By similar arguments, we have a contradiction
when we suppose $(z,w)=(v_{5},v_{2})$.

We next suppose $(x,w)\in A_{(u,v)}^{-1}$ and $(w,z)\notin A_{(u,v)}^{-1}$. We
have $(w,x)\in A_{(u,v)}\subseteq F$ and $(w,z)\in F$ but $(w,z)\notin
A_{(u,v)}$. Since $(w,x)\in A_{(u,v)}$, there is a regular obstruction
$(u,v,v_{2},v_{3},v_{4},v_{5})$ of $P+F$ such that $(u,v)$ is its base and
$(w,x)$ is its front. Suppose $(w,x)=(v_{4},v_{3})$ (Fig. 88(d)). We have
$(v_{2},z)\in P$ from $(v_{2},v_{3}),(v_{3},y),(y,z)\in P$. Then
$(u,v,v_{2},z,v_{4},v_{5})$ is a regular obstruction, and hence $(v_{4},z)\in
A_{(u,v)}$, a contradiction. Suppose $(w,x)=(v_{4},v_{2})$. We have
$(v_{2},z)\in P$ from $(v_{2},y),(y,z)\in P$. Then $(u,v,v_{2},z,v_{4},v_{5})$
is a regular obstruction, and hence $(v_{4},z)\in A_{(u,v)}$, a contradiction.

Suppose $(w,x)=(v_{5},v_{3})$ (Fig. 88(e)). We have $(v_{2},z)\in P$ from
$(v_{2},v_{3}),(v_{3},y),(y,z)\in P$. We also have $(v,v_{4}),(v_{4},v_{2})\in
F$ from Proposition 14. If $(z,v)\in P$ then $(v_{2},z)\in P$ implies
$(v_{2},v)\in P$, contradicting $(v_{2},v)\in F$. If $(v,z)\in P$ then
$(u,v,z,v_{5})$ is a forbidden configuration for $\mathbf{3+1}$ in $P+F$, a
contradiction. Thus $vz\in E(\overline{G})$. Proposition 9 implies that the
vertices $v_{2},y,z,v$ induce $K_{1,3}$ in $\overline{G}$. Then we have
$(z,v)\in F$ from $(v_{2},v)\in F$. If $(v_{4},z)\in P$ then $(v_{4},z,v)$ is
a forbidden configuration for $\mathbf{2+1}$ in $P+F$, a contradiction. If
$(z,v_{4})\in P$ then $(v_{4},v_{5})\in P$ implies $(z,v_{5})\in P$,
contradicting $(v_{5},z)\in F$. Thus $v_{4}z\in E(\overline{G})$. Proposition
9 implies that the vertices $v_{2},y,z,v_{4}$ induce $K_{1,3}$ in
$\overline{G}$, and we have $(v_{4},z)\in F$ from $(v_{4},v_{2})\in F$. Then
$(u,v,v_{2},z,v_{4},v_{5})$ is a regular obstruction, and hence $(v_{5},z)\in
A_{(u,v)}$, a contradiction. By similar arguments, we have a contradiction
when we suppose $(z,w)=(v_{5},v_{2})$. ∎

######  Claim 16.

The orientation $P+F^{\prime}$ contains no forbidden configurations for
$\mathbf{2+1}$.

###### Proof of Claim 16.

Suppose that $P+F^{\prime}$ contains a forbidden configuration $(x,y,z)$ for
$\mathbf{2+1}$. If $(y,z),(z,x)\in A_{(u,v)}^{-1}$ then we have from Claim 13
that $(y,z)\in A_{(u,v)}^{-1}$ implies $(u,z)\in F$ and $(z,x)\in
A_{(u,v)}^{-1}$ implies $(z,u)\in F$, a contradiction. Thus either $(y,z)\in
A_{(u,v)}^{-1}$ or $(z,x)\in A_{(u,v)}^{-1}$.

We first suppose $(y,z)\in A_{(u,v)}^{-1}$ and $(z,x)\notin A_{(u,v)}^{-1}$.
We have $(z,y)\in A_{(u,v)}\subseteq F$ and $(z,x)\in F$ but $(z,x)\notin
A_{(u,v)}$. Since $(z,y)\in A_{(u,v)}$, there is a regular obstruction
$(u,v,v_{2},v_{3},v_{4},v_{5})$ of $P+F$ such that $(u,v)$ is its base and
$(z,y)$ is its front. Suppose $(z,y)=(v_{4},v_{3})$ (Fig. 88(f)). We have
$(v_{3},u),(v,v_{4})\in F$ from Proposition 14. If $(v,x)\in P$ then
$(u,v),(x,v_{3})\in P$ implies $(u,v_{3})\in P$, contradicting $(v_{3},u)\in
F$. If $(x,v)\in P$ then $(x,v,v_{4})$ is a forbidden configuration for
$\mathbf{2+1}$ in $P+F$, a contradiction. Thus $vx\in E(\overline{G})$.
Proposition 8 implies that $(u,x,v,v_{3})$ is $C_{4}$ in $\overline{G}$, and
we have $(x,v)\in F$ from $(v_{3},u)\in F$. Then $(u,v,x,v_{3},v_{4},v_{5})$
is a regular obstruction, and hence $(v_{4},x)\in A_{(u,v)}$, a contradiction.
When we suppose $(z,w)=(v_{4},v_{2})$, we have $(x,v_{3})\in P$ from
$(x,v_{2}),(v_{2},v_{3})\in P$. Thus by similar arguments, we have a
contradiction.

Suppose $(z,y)=(v_{5},v_{3})$ (Fig. 88(g)). We have $(v_{3},u),(v,v_{5})\in F$
from Proposition 14. If $(v,x)\in P$ then $(u,v),(x,v_{3})\in P$ implies
$(u,v_{3})\in P$, contradicting $(v_{3},u)\in F$. If $(x,v)\in P$ then
$(x,v,v_{5})$ is a forbidden configuration for $\mathbf{2+1}$ in $P+F$, a
contradiction. Thus $vx\in E(\overline{G})$. Proposition 8 implies that
$(u,x,v,v_{3})$ is $C_{4}$ in $\overline{G}$, and we have $(x,v)\in F$ from
$(v_{3},u)\in F$. Then $(u,v,x,v_{3},v_{4},v_{5})$ is a regular obstruction,
and hence $(v_{5},x)\in A_{(u,v)}$, a contradiction. When we suppose
$(z,y)=(v_{5},v_{2})$, we have $(x,v_{3})\in P$ from
$(x,v_{2}),(v_{2},v_{3})\in P$. Thus by similar arguments, we have a
contradiction.

We next suppose $(z,x)\in A_{(u,v)}^{-1}$ and $(y,z)\notin A_{(u,v)}^{-1}$. We
have $(x,z)\in A_{(u,v)}\subseteq F$ and $(y,z)\in F$ but $(y,z)\notin
A_{(u,v)}$. Since $(x,z)\in A_{(u,v)}$, there is a regular obstruction
$(u,v,v_{2},v_{3},v_{4},v_{5})$ of $P+F$ such that $(u,v)$ is its base and
$(x,z)$ is its front. Suppose $(x,z)=(v_{4},v_{3})$ (Fig. 88(h)). We have
$(v_{3},u),(v,v_{4})\in F$ from Proposition 14. If $(y,u)\in P$ then
$(v_{4},y),(u,v)\in P$ implies $(v_{4},v)\in P$, contradicting $(v,v_{4})\in
F$. If $(u,y)\in P$ then $(u,y,v_{3})$ is a forbidden configuration for
$\mathbf{2+1}$ in $P+F$, a contradiction. Thus $uy\in E(\overline{G})$.
Proposition 8 implies that $(u,v_{4},v,y)$ is $C_{4}$ in $\overline{G}$, and
we have $(u,y)\in F$ from $(v,v_{4})\in F$. Then $(u,v,v_{2},v_{3},v_{4},y)$
is a regular obstruction, and hence $(y,v_{2})\in A_{(u,v)}$, a contradiction.
When we suppose $(x,z)=(v_{5},v_{3})$, we have $(v_{4},y)\in P$ from
$(v_{4},v_{5}),(v_{5},y)\in P$. Thus by similar arguments, we have a
contradiction.

Suppose $(x,z)=(v_{4},v_{2})$ (Fig. 88(i)). We have $(v_{2},u),(v,v_{4})\in F$
from Proposition 14. If $(y,u)\in P$ then $(v_{4},y),(u,v)\in P$ implies
$(v_{4},v)\in P$, contradicting $(v,v_{4})\in F$. If $(u,y)\in P$ then
$(u,y,v_{2})$ is a forbidden configuration for $\mathbf{2+1}$ in $P+F$, a
contradiction. Thus $uy\in E(\overline{G})$. Proposition 8 implies that
$(u,v_{4},v,y)$ is $C_{4}$ in $\overline{G}$, and we have $(u,y)\in F$ from
$(v,v_{4})\in F$. Then $(u,v,v_{2},v_{3},v_{4},y)$ is a regular obstruction,
and hence $(y,v_{2})\in A_{(u,v)}$, a contradiction. When we suppose
$(x,z)=(v_{5},v_{2})$, we have $(v_{4},y)\in P$ from
$(v_{4},v_{5}),(v_{5},y)\in P$. Thus by similar arguments, we have a
contradiction. ∎

$v_{0}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v$$u$ Figure 9.  Illustrating the
proof of Claim 17. Arrows, dashed arrows, and dashed lines denote the same
type of edges as in Fig. 5.

######  Claim 17.

No edge in $A_{(u,v)}^{-1}$ is an edge of a regular obstruction of
$P+F^{\prime}$. That is, reversing the direction of the edges in $A_{(u,v)}$
generates no new regular obstructions.

###### Proof of Claim 17.

Suppose that $P+F^{\prime}$ contains a regular obstruction
$(v_{0},v_{1},v_{2},v_{3},v_{4},v_{5})$. Assume without loss of generality
$(v_{4},v_{3})\in A_{(u,v)}^{-1}$. Suppose $(v_{0},v_{5})\in A_{(u,v)}^{-1}$.
We have from Claim 13 that $(v_{4},v_{3})\in A_{(u,v)}^{-1}$ implies
$(v_{4},v)\in F$ and $(v_{0},v_{5})\in A_{(u,v)}^{-1}$ implies $(u,v_{5})\in
F$. Thus $(u,v,v_{4},v_{5})$ is a forbidden configuration for $\mathbf{2+2}$
in $P+F$, a contradiction. Thus $(v_{0},v_{5})\notin A_{(u,v)}^{-1}$.
Similarly, we have $(v_{2},v_{1})\notin A_{(u,v)}^{-1}$.

Now, $(v_{3},v_{4})\in A_{(u,v)}\subseteq F$ and
$(v_{0},v_{5}),(v_{2},v_{1})\in F$ but $(v_{0},v_{5}),(v_{2},v_{1})\notin
A_{(u,v)}$. Claim 13 implies $(u,v_{3}),(v,v_{3}),(v_{4},u),(v_{4},v)\in F$
(Fig. 9). If $(v_{0},v)\in P$ then $(v_{0},v,v_{4},v_{5})$ is a forbidden
configuration for $\mathbf{2+2}$ in $P+F$, a contradiction. If $(v,v_{0})\in
P$ then $(v_{0},v_{1})\in P$ implies $(v,v_{1})\in P$, but then
$(v,v_{1},v_{2},v_{3})$ is a forbidden configuration for $\mathbf{2+2}$ in
$P+F$, a contradiction. Thus $vv_{0}\in E(\overline{G})$. If $(v_{1},u)\in P$
then $(v_{0},v_{1}),(u,v)\in P$ implies $(v_{0},v)\in P$, contradicting
$vv_{0}\in E(\overline{G})$. If $(u,v_{1})\in P$ then $(u,v_{1},v_{2},v_{3})$
is a forbidden configuration for $\mathbf{2+2}$ in $P+F$, a contradiction.
Thus $uv_{1}\in E(\overline{G})$. Proposition 8 implies that
$(u,v_{0},v,v_{1})$ is $C_{4}$ in $\overline{G}$. If $(v,v_{0}),(u,v_{1})\in
F$ then $(u,v,v_{4},v_{5},v_{0},v_{1})$ is a regular obstruction, and hence
$(v_{0},v_{5})\in A_{(u,v)}$, a contradiction. If $(v_{0},v),(v_{1},u)\in F$
then $(u,v,v_{0},v_{1},v_{2},v_{3})$ is a regular obstruction, and hence
$(v_{2},v_{1})\in A_{(u,v)}$, a contradiction. ∎

The following is trivial from the definition of $A_{(u,v)}$.

######  Claim 18.

The orientation $P+F^{\prime}$ contains no regular obstructions with base
$(u,v)$.

Claims 14–18 ensure that by repeating the procedure for each edge of $P$, we
can obtain an orientation $F^{\prime\prime}$ of $E_{o}$ such that
$P+F^{\prime\prime}$ contains no forbidden configurations for $\mathbf{2+2}$,
$\mathbf{3+1}$, or $\mathbf{2+1}$, and $P+F^{\prime\prime}$ contains no
regular obstructions.

Now, let $F$ be an orientation of $E_{o}$ such that $P+F$ contains no
forbidden configurations for $\mathbf{2+2}$, $\mathbf{3+1}$, or
$\mathbf{2+1}$, and $P+F$ contains no regular obstructions. Then, let $(u,v)$
be an edge in $P$. We define that

$\displaystyle B_{(u,v)}$ $\displaystyle=\\{(x,y)\in F\colon\ \text{there is a
skewed obstruction such that $(u,v)$ is its base and $(x,y)$ is its
front}\\},$ $\displaystyle B_{(u,v)}^{-1}$ $\displaystyle=\\{(y,x)\colon\
(x,y)\in B_{(u,v)}\\},\text{ and }$ $\displaystyle F^{\prime}$
$\displaystyle=(F-B_{(u,v)})+B_{(u,v)}^{-1}.$

In other words, $F^{\prime}$ is an orientation of $E_{o}$ obtained from $F$ by
reversing the direction of all edges in $B_{(u,v)}$.

$u$$v$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$w$$x$ (a)

$u$$v$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$x$$y$ (b)
$u$$v$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$y$$z$ (c)
$u$$v$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$y$$z$ (d)

$u$$v$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$x$ (e)
$u$$v$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$x$ (f)
$u$$v$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$y$ (g)

Figure 10.  Illustrating the proof of Claims 19–21. Arrows and dashed arrows
denote the same type of edges as in Fig. 5.

######  Claim 19.

The orientation $P+F^{\prime}$ contains no forbidden configurations for
$\mathbf{2+2}$.

###### Proof of Claim 19.

Suppose that $P+F^{\prime}$ contains a forbidden configuration $(x,y,z,w)$ for
$\mathbf{2+2}$. If $(z,y),(x,w)\in B_{(u,v)}^{-1}$ then $(y,z),(w,x)\in F$,
that is, $(x,y,z,w)$ is an alternating cycle of length 4 in $P+F$,
contradicting Proposition 16. Thus either $(z,y)\in B_{(u,v)}^{-1}$ or
$(x,w)\in B_{(u,v)}^{-1}$. Assume without loss of generality $(z,y)\in
B_{(u,v)}^{-1}$ and $(x,w)\notin B_{(u,v)}^{-1}$. Then $(y,z)\in
B_{(u,v)}\subseteq F$ and $(x,w)\in F$ but $(x,w)\notin B_{(u,v)}$.

Since $(y,z)\in B_{(u,v)}$, there is a skewed obstruction
$(u,v,v_{2},v_{3},v_{4},v_{5})$ of $P+F$ such that $(u,v)$ is its base and
$(y,z)$ is its front. Suppose $(y,z)=(v_{4},v_{3})$ (Fig. 1010(a)). We have
$(x,v_{5})\in P$ from $(x,v_{4}),(v_{4},v_{5})\in P$. We also have
$(v_{3},v)\in F$ from Proposition 15. Then $(u,v,v_{3},w,x,v_{5})$ is a
regular obstruction of $P+F$, a contradiction. By similar arguments, we have a
contradiction when we suppose $(y,z)=(v_{5},v_{3})$. ∎

######  Claim 20.

The orientation $P+F^{\prime}$ contains no forbidden configurations for
$\mathbf{3+1}$.

###### Proof of Claim 20.

Suppose that $P+F^{\prime}$ contains a forbidden configuration $(x,y,z,w)$ for
$\mathbf{3+1}$. Note that $(x,y),(y,z)\in P$ implies $(x,z)\in P$. If
$(w,z),(x,w)\in B_{(u,v)}^{-1}$ then $(z,w),(w,x)\in F$, that is, $(x,z,w)$ is
a forbidden configuration for $\mathbf{2+1}$ in $P+F$, a contradiction. Thus
either $(w,z)\in B_{(u,v)}^{-1}$ or $(x,w)\in B_{(u,v)}^{-1}$.

We first suppose $(w,z)\in B_{(u,v)}^{-1}$ and $(x,w)\notin B_{(u,v)}^{-1}$.
We have $(z,w)\in B_{(u,v)}\subseteq F$ and $(x,w)\in F$ but $(x,w)\notin
B_{(u,v)}$. Since $(z,w)\in B_{(u,v)}$, there is a skewed obstruction
$(u,v,v_{2},v_{3},v_{4},v_{5})$ of $P+F$ such that $(u,v)$ is its base and
$(z,w)$ is its front. Suppose $(z,w)=(v_{4},v_{3})$ (Fig. 1010(b)). We have
$(x,v_{5})\in P$ from $(x,y),(y,v_{4}),(v_{4},v_{5})\in P$. Then
$(u,v,v_{2},v_{3},x,v_{5})$ is a skewed obstruction, and hence $(x,v_{3})\in
B_{(u,v)}$, a contradiction. By similar arguments, we have a contradiction
when we suppose $(y,z)=(v_{5},v_{3})$.

We next suppose $(x,w)\in B_{(u,v)}^{-1}$ and $(w,z)\notin B_{(u,v)}^{-1}$. We
have $(w,x)\in B_{(u,v)}\subseteq F$ and $(w,z)\in F$ but $(w,z)\notin
B_{(u,v)}$. Since $(w,x)\in B_{(u,v)}$, there is a skewed obstruction
$(u,v,v_{2},v_{3},v_{4},v_{5})$ of $P+F$ such that $(u,v)$ is its base and
$(w,x)$ is its front. Suppose $(w,x)=(v_{4},v_{3})$ (Fig. 1010(c)). We have
$(v_{3},v)\in F$ from Proposition 15. Then $(u,v,v_{3},z,v_{4},v_{5})$ is a
regular obstruction of $P+F$, a contradiction.

Suppose $(w,x)=(v_{5},v_{3})$ (Fig. 1010(d)). We have $(v_{3},v),(v,v_{4})\in
F$ from Proposition 15. If $(z,v)\in P$ then $(v_{3},z)\in P$ implies
$(v_{3},v)\in P$, contradicting $(v_{3},v)\in F$. If $(v,z)\in P$ then
$(u,v,z,v_{5})$ is a forbidden configuration for $\mathbf{3+1}$ in $P+F$, a
contradiction. Thus $vz\in E(\overline{G})$. Proposition 8 implies that
$(v,v_{3},v_{2},z)$ is $C_{4}$ in $\overline{G}$. Then we have $(z,v)\in F$
from $(v_{3},v_{2})\in F$. If $(v_{4},z)\in P$ then $(v_{4},z,v)$ is a
forbidden configuration for $\mathbf{2+1}$ in $P+F$, a contradiction. If
$(z,v_{4})\in P$ then $(v_{4},v_{5})\in P$ implies $(z,v_{5})\in P$,
contradicting $(v_{5},z)\in F$. Thus $v_{4}z\in E(\overline{G})$. Proposition
9 implies that the vertices $v_{3},y,z,v_{4}$ induce $K_{1,3}$ in
$\overline{G}$, and we have $(v_{4},z)\in F$ from $(v_{4},v_{3})\in F$. Then
$(u,v,v_{3},z,v_{4},v_{5})$ is a regular obstruction of $P+F$, a
contradiction. ∎

######  Claim 21.

The orientation $P+F^{\prime}$ contains no forbidden configurations for
$\mathbf{2+1}$.

###### Proof of Claim 21.

Suppose that $P+F^{\prime}$ contains a forbidden configuration $(x,y,z)$ for
$\mathbf{2+1}$. If $(y,z),(z,x)\in B_{(u,v)}^{-1}$ then we have from Claim 13
that $(y,z)\in B_{(u,v)}^{-1}$ implies $(u,z)\in F$ and $(z,x)\in
B_{(u,v)}^{-1}$ implies $(z,u)\in F$, a contradiction. Thus either $(y,z)\in
B_{(u,v)}^{-1}$ or $(z,x)\in B_{(u,v)}^{-1}$.

We first suppose $(y,z)\in B_{(u,v)}^{-1}$ and $(z,x)\notin B_{(u,v)}^{-1}$.
We have $(z,y)\in B_{(u,v)}\subseteq F$ and $(z,x)\in F$ but $(z,x)\notin
B_{(u,v)}$. Since $(z,y)\in B_{(u,v)}$, there is a skewed obstruction
$(u,v,v_{2},v_{3},v_{4},v_{5})$ of $P+F$ such that $(u,v)$ is its base and
$(z,y)$ is its front. Suppose $(z,y)=(v_{4},v_{3})$ (Fig. 1010(e)). We have
$(v_{3},u),(v,v_{4})\in F$ from Proposition 15. If $(v,x)\in P$ then
$(u,v),(x,v_{3})\in P$ implies $(u,v_{3})\in P$, contradicting $(v_{3},u)\in
F$. If $(x,v)\in P$ then $(x,v,v_{4})$ is a forbidden configuration for
$\mathbf{2+1}$ in $P+F$, a contradiction. Thus $vx\in E(\overline{G})$.
Proposition 8 implies that $(u,x,v,v_{3})$ is $C_{4}$ in $\overline{G}$, and
we have $(x,v)\in F$ from $(v_{3},u)\in F$. Then $(u,v,x,v_{3},v_{4},v_{5})$
is a regular obstruction of $P+F$, a contradiction.

Suppose $(z,y)=(v_{5},v_{3})$ (Fig. 1010(f)). We have $(v_{3},u),(v,v_{5})\in
F$ from Proposition 15. If $(v,x)\in P$ then $(u,v),(x,v_{3})\in P$ implies
$(u,v_{3})\in P$, contradicting $(v_{3},u)\in F$. If $(x,v)\in P$ then
$(x,v,v_{5})$ is a forbidden configuration for $\mathbf{2+1}$ in $P+F$, a
contradiction. Thus $vx\in E(\overline{G})$. Proposition 8 implies that
$(u,x,v,v_{3})$ is $C_{4}$ in $\overline{G}$, and we have $(x,v)\in F$ from
$(v_{3},u)\in F$. Then $(u,v,x,v_{3},v_{4},v_{5})$ is a regular obstruction of
$P+F$, a contradiction.

We next suppose $(z,x)\in B_{(u,v)}^{-1}$ and $(y,z)\notin B_{(u,v)}^{-1}$. We
have $(x,z)\in B_{(u,v)}\subseteq F$ and $(y,z)\in F$ but $(y,z)\notin
B_{(u,v)}$. Since $(x,z)\in B_{(u,v)}$, there is a skewed obstruction
$(u,v,v_{2},v_{3},v_{4},v_{5})$ of $P+F$ such that $(u,v)$ is its base and
$(x,z)$ is its front. Suppose $(x,z)=(v_{4},v_{3})$ (Fig. 1010(g)). We have
$(v_{3},u),(v,v_{4})\in F$ from Proposition 15. If $(y,u)\in P$ then
$(v_{4},y),(u,v)\in P$ implies $(v_{4},v)\in P$, contradicting $(v,v_{4})\in
F$. If $(u,y)\in P$ then $(u,y,v_{3})$ is a forbidden configuration for
$\mathbf{2+1}$ in $P+F$, a contradiction. Thus $uy\in E(\overline{G})$.
Proposition 8 implies that $(u,v_{4},v,y)$ is $C_{4}$ in $\overline{G}$, and
we have $(u,y)\in F$ from $(v,v_{4})\in F$. Then $(u,v,v_{2},v_{3},v_{4},y)$
is a skewed obstruction, and hence $(y,v_{3})\in B_{(u,v)}$, a contradiction.
When we suppose $(x,z)=(v_{5},v_{3})$, we have $(v_{4},y)\in P$ from
$(v_{4},v_{5}),(v_{5},y)\in P$. Thus by similar arguments, we have a
contradiction. ∎

######  Claim 22.

The orientation $P+F^{\prime}$ contains no regular obstructions.

###### Proof of Claim 22.

As in the proof of Claim 17, if $P+F^{\prime}$ contains a regular obstruction,
then $P+F$ also contains a regular obstruction, a contradiction. ∎

$v_{0}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v$$u$ (a)

$u$$v$$u_{2}$$u_{3}$$u_{4}$$u_{5}$$v_{4}$$v_{5}$$v_{0}$$v_{1}$ (b)
$u$$v$$u_{2}$$u_{3}$$u_{4}$$u_{5}$$v_{4}$$v_{5}$$v_{0}$$v_{1}$ (c)

$u$$v$$u_{2}$$v_{4}$$u_{4}$$u_{5}$$u_{3}$$v_{0}$$v_{1}$$v_{2}$ (d)
$u$$v$$u_{2}$$v_{4}$$u_{4}$$u_{5}$$u_{3}$$v_{0}$$v_{1}$$v_{2}$ (e)

Figure 11.  Illustrating the proof of Claim 23. Arrows, dashed arrows, and
dashed lines denote the same type of edges as in Fig. 5.

######  Claim 23.

If $P+F$ contains no skewed obstructions with base $(v_{0},v_{1})$, then
$P+F^{\prime}$ contains no skewed obstructions with base $(v_{0},v_{1})$.

###### Proof of Claim 23.

Suppose that $P+F^{\prime}$ contains a skewed obstruction
$(v_{0},v_{2},v_{2},v_{3},v_{4},v_{5})$ with base $(v_{0},v_{1})$ whereas
$P+F$ does not contain this obstruction.

Suppose $(v_{0},v_{5})\in B_{(u,v)}^{-1}$. From Claim 13, we have
$(u,v_{5}),(v,v_{5}),(v_{0},u),(v_{0},v)\in F$. If $(v_{4},v_{3})\in
B_{(u,v)}^{-1}$ then from Claim 13, we have $(v_{4},v)\in F$, and hence
$(u,v,v_{4},v_{5})$ is a forbidden configuration for $\mathbf{2+2}$ in $P+F$,
a contradiction. If $(v_{5},v_{3})\in B_{(u,v)}^{-1}$ then from Claim 13, we
have $(v_{5},u),(v_{5},v)\in F$, contradicting $(u,v_{5}),(v,v_{5})\in F$. If
$(v_{3},v_{2})\in B_{(u,v)}^{-1}$ then from Claim 13, we have $(u,v_{2})\in
F$, and hence $(u,v,v_{0},v_{2})$ is a forbidden configuration for
$\mathbf{2+2}$ in $P+F$, a contradiction. Therefore,
$(v_{4},v_{3}),(v_{5},v_{3}),(v_{3},v_{2})\notin B_{(u,v)}^{-1}$.

Now, $(v_{5},v_{0})\in B_{(u,v)}\subseteq F$ and
$(v_{4},v_{3}),(v_{5},v_{3}),(v_{3},v_{2})\in F$ but
$(v_{4},v_{3}),(v_{5},v_{3}),(v_{3},v_{2})\notin B_{(u,v)}$. From Claim 13, we
have $(u,v_{5}),(v,v_{5}),(v_{0},u),(v_{0},v)\in F$ (Fig. 1111(a)). If
$(v_{4},v_{1})\in P$ then $(v_{4},v_{1},v_{2},v_{3})$ is a forbidden
configuration for $\mathbf{3+1}$ in $P+F$, a contradiction. If
$(v_{1},v_{4})\in P$ then $(v_{0},v_{1}),(v_{4},v_{5})\in P$ implies
$(v_{0},v_{5})\in P$, contradicting $(v_{5},v_{0})\in F$. Thus $v_{4}v_{1}\in
E(\overline{G})$. Proposition 8 implies that $(v_{4},v_{0},v_{5},v_{1})$ is
$C_{4}$ in $\overline{G}$, and we have $(v_{4},v_{1})\in F$ from
$(v_{5},v_{0})\in F$. Then $(u,v,v_{0},v_{1},v_{4},v_{5})$ is a regular
obstruction of $P+F$, a contradiction.

Suppose $(v_{3},v_{2})\in B_{(u,v)}^{-1}$. From Claim 13, we have
$(u,v_{2}),(v,v_{2}),(v_{3},u),(v_{3},v)\in F$. If $(v_{4},v_{3})\in
B_{(u,v)}^{-1}$ or $(v_{5},v_{3})\in B_{(u,v)}^{-1}$, then from Claim 13, we
have $(u,v_{3}),(v,v_{3})\in F$, contradicting $(v_{3},u),(v_{3},v)\in F$. If
$(v_{0},v_{5})\in B_{(u,v)}^{-1}$ then from Claim 13, we have $(v_{0},v)\in
F$, and thus $(u,v,v_{0},v_{2})$ is a forbidden configuration for
$\mathbf{2+2}$ in $P+F$, a contradiction. Therefore,
$(v_{4},v_{3}),(v_{5},v_{3}),(v_{0},v_{5})\notin B_{(u,v)}^{-1}$.

Now, $(v_{2},v_{3})\in B_{(u,v)}\subseteq F$ and
$(v_{4},v_{3}),(v_{5},v_{3}),(v_{0},v_{5})\in F$ but
$(v_{4},v_{3}),(v_{5},v_{3}),(v_{0},v_{5})\notin B_{(u,v)}$. Since
$(v_{2},v_{3})\in B_{(u,v)}$, there is a skewed obstruction
$(u,v,u_{2},u_{3},u_{4},u_{5})$ of $P+F$ such that $(u,v)$ is its base and
$(v_{2},v_{3})$ is its front. Suppose $(v_{2},v_{3})=(u_{4},u_{3})$ (Fig.
1111(b)). We have $(v_{0},u_{5})\in P$ from
$(v_{0},v_{1}),(v_{1},u_{4}),(u_{4},u_{5})\in P$. If $(u,v_{5})\in P$ then
$(u,v_{5},v_{0},u_{5})$ is a forbidden configuration for $\mathbf{2+2}$ in
$P+F$, a contradiction. If $(v_{4},v)\in P$ then $(v_{4},v,u_{2},u_{3})$ is a
forbidden configuration for $\mathbf{3+1}$ in $P+F$, a contradiction. If
$(v_{5},u)\in P$ then $(v_{4},v_{5}),(u,v)\in P$ implies $(v_{4},v)\in P$, a
contradiction. If $(v,v_{4})\in P$ then $(u,v),(v_{4},v_{5})\in P$ implies
$(u,v_{5})\in P$, a contradiction. Thus $uv_{5},vv_{4}\in E(\overline{G})$.
Proposition 8 implies that $(u,v_{4},v,v_{5})$ is $C_{4}$ in $\overline{G}$.
If $(u,v_{5}),(v,v_{4})\in F$ then $(u,v,u_{2},u_{3},v_{4},v_{5})$ is a skewed
obstruction, and hence $(v_{4},u_{3})\in B_{(u,v)}$, a contradiction. If
$(v_{5},u),(v_{4},v)\in F$ then $(u,v,v_{4},v_{5},v_{0},u_{5})$ is a regular
obstruction of $P+F$, a contradiction. When we suppose
$(v_{2},v_{3})=(u_{5},u_{3})$ (Fig. 1111(c)), we have $(v_{0},u_{5})\in P$
from $(v_{0},v_{1}),(v_{1},u_{5})\in P$. Thus by similar arguments, we have a
contradiction.

Suppose $(v_{5},v_{3})\in B_{(u,v)}^{-1}$. From Claim 13, we have
$(u,v_{3}),(v,v_{3}),(v_{5},u),(v_{5},v)\in F$. If $(v_{3},v_{2})\in
B_{(u,v)}^{-1}$ then from Claim 13, we have $(v_{3},u),(v_{3},v)\in F$,
contradicting $(u,v_{3}),(v,v_{3})\in F$. If $(v_{0},v_{5})\in B_{(u,v)}^{-1}$
then from Claim 13, we have $(u,v_{5}),(v,v_{5})\in F$, contradicting
$(v_{5},u),(v_{5},v)\in F$. Therefore, $(v_{3},v_{2}),(v_{0},v_{5})\notin
B_{(u,v)}^{-1}$.

Now, $(v_{3},v_{5})\in B_{(u,v)}\subseteq F$ and
$(v_{3},v_{2}),(v_{0},v_{5})\in F$ but $(v_{3},v_{2}),(v_{0},v_{5})\notin
B_{(u,v)}$. Note that it does not matter whether $(v_{4},v_{3})\in
B_{(u,v)}^{-1}$ or $(v_{4},v_{3})\notin B_{(u,v)}^{-1}$. Since
$(v_{3},v_{5})\in B_{(u,v)}$, there is a skewed obstruction
$(u,v,u_{2},u_{3},u_{4},u_{5})$ of $P+F$ such that $(u,v)$ is its base and
$(v_{3},v_{5})$ is its front. Suppose $(v_{3},v_{5})=(u_{4},u_{3})$ (Fig.
1111(d)). If $(u,v_{1})\in P$ then $(v_{1},v_{2})\in P$ implies $(u,v_{2})\in
P$. Thus $(u,v_{2},u_{4},u_{5})$ is a forbidden configuration for
$\mathbf{2+2}$ in $P+F$, a contradiction. If $(v_{0},v)\in P$ then
$(v_{0},v,u_{2},u_{3})$ is a forbidden configuration for $\mathbf{3+1}$ in
$P+F$, a contradiction. If $(v_{1},u)\in P$ then $(v_{0},v_{1}),(u,v)\in P$
implies $(v_{0},v)\in P$, a contradiction. If $(v,v_{0})\in P$ then
$(u,v),(v_{0},v_{1})\in P$ implies $(u,v_{1})\in P$, a contradiction. Thus
$uv_{1},vv_{0}\in E(\overline{G})$. Proposition 8 implies that
$(u,v_{0},v,v_{1})$ is $C_{4}$ in $\overline{G}$. If $(u,v_{1}),(v,v_{0})\in
F$ then $(u,v,u_{2},u_{3},v_{0},v_{1})$ is a skewed obstruction, and hence
$(v_{0},u_{3})\in B_{(u,v)}$, a contradiction. If $(v_{1},u),(v_{0},v)\in F$
then $(u,v,v_{0},v_{2},u_{4},u_{5})$ is a regular obstruction of $P+F$, a
contradiction.

Suppose $(v_{3},v_{5})=(u_{5},u_{3})$ (Fig. 1111(e)). If $(u,v_{1})\in P$ then
$(u,v_{1},v_{2},u_{5})$ is a forbidden configuration for $\mathbf{3+1}$ in
$P+F$, a contradiction. If $(v_{0},v)\in P$ then $(v_{0},v,u_{2},u_{3})$ is a
forbidden configuration for $\mathbf{3+1}$ in $P+F$, a contradiction. If
$(v_{1},u)\in P$ then $(v_{0},v_{1}),(u,v)\in P$ implies $(v_{0},v)\in P$, a
contradiction. If $(v,v_{0})\in P$ then $(u,v),(v_{0},v_{1})\in P$ implies
$(u,v_{1})\in P$, a contradiction. Thus $uv_{1},vv_{0}\in E(\overline{G})$.
Proposition 8 implies that $(u,v_{0},v,v_{1})$ is $C_{4}$ in $\overline{G}$.
If $(u,v_{1}),(v,v_{0})\in F$ then $(u,v,u_{2},u_{3},v_{0},v_{1})$ is a skewed
obstruction, and hence $(v_{0},u_{3})\in B_{(u,v)}$, a contradiction. If
$(v_{1},u),(v_{0},v)\in F$ then $(v_{0},v_{1},v_{2},u_{5},u,v)$ is a skewed
obstruction with base $(v_{0},v_{1})$, contradicting the assumption that $P+F$
contains no skewed obstructions with base $(v_{0},v_{1})$.

Suppose $(v_{4},v_{3})\in B_{(u,v)}^{-1}$. If $(v_{5},v_{3})\notin
B_{(u,v)}^{-1}$ then $(v_{5},v_{3}),(v_{3},v_{4})\in F$, that is,
$(v_{4},v_{5},v_{3})$ is a forbidden configuration for $\mathbf{2+1}$ in
$P+F$, a contradiction. Thus we have $(v_{5},v_{3})\in B_{(u,v)}^{-1}$, a
contradiction. ∎

The following is trivial from the definition of $B_{(u,v)}$.

######  Claim 24.

The orientation $P+F^{\prime}$ contains no skewed obstructions with base
$(u,v)$.

Claims 19–24 ensure that by repeating the procedure for each edge of $P$, we
can obtain an orientation $F^{\prime\prime}$ of $E_{o}$ such that
$P+F^{\prime\prime}$ contains no forbidden configurations for $\mathbf{2+2}$,
$\mathbf{3+1}$, or $\mathbf{2+1}$, and $P+F^{\prime\prime}$ contains no
obstructions. Therefore, we can compute the orientation by Algorithm 3.

Input: An orientation $F$ of $E_{o}$ such that $P+F$ contains no forbidden
configurations.

Output: An orientation $F^{\prime}$ of $E_{o}$ such that $P+F^{\prime}$
contains no forbidden configurations nor no obstructions.

1

2foreach  _$(u,v)\in P$_ do /* remove regular obstructions */

3 $A_{(u,v)}\leftarrow\emptyset$;

4 foreach  _pair $(v_{4},v_{3}),(v_{5},v_{2})\in F$_ do

5 if  _$(v_{2},v_{3}),(v_{4},v_{5})\in P$ and $(v_{2},v),(u,v_{5})\in F$_ then

6 $A_{(u,v)}\leftarrow
A_{(u,v)}+\\{(v_{4},v_{3}),(v_{5},v_{3}),(v_{4},v_{2}),(v_{5},v_{2})\\}$;

7

8 end if

9

10 end foreach

11 $F\leftarrow(F-A_{(u,v)})+A_{(u,v)}^{-1}$;

12

13 end foreach

14foreach  _$(u,v)\in P$_ do /* remove skewed obstructions */

15 $B_{(u,v)}\leftarrow\emptyset$;

16 foreach  _pair $(v_{4},v_{3}),(v_{5},v_{2})\in F$_ do

17 if  _$(v,v_{2}),(v_{4},v_{5})\in P$ and
$(v_{3},v_{2}),(v_{5},v_{3}),(u,v_{5})\in F$_ then

18 $B_{(u,v)}\leftarrow B_{(u,v)}+\\{(v_{4},v_{3}),(v_{5},v_{3})\\}$;

19

20 end if

21

22 end foreach

23 $F\leftarrow(F-B_{(u,v)})+B_{(u,v)}^{-1}$;

24

25 end foreach

26return _$F$_ ;

Algorithm 3 Algorithm for Lemma 17

Each iteration on lines 3–7 takes $O(1)$ time for each pair of edges of $F$.
Hence $A_{(u,v)}$ can be constructed in $O(\bar{m}^{2})$ time and
$|A_{(u,v)}|=O(\bar{m}^{2})$. Therefore, we can remove all regular
obstructions in $O(m\bar{m}^{2})$ time (lines 1–9). Similarly, we can remove
all skewed obstructions in $O(m\bar{m}^{2})$ time (lines 10–18). Hence
Algorithm 3 takes $O(m\bar{m}^{2})$ time. ∎

Now from the lemmas above, we have the main theorem and the following
characterization.

######  Theorem 18.

A partial order $P$ on a set $V$ is a linear-semiorder if and only if there is
an orientation $F$ of $E_{o}$ (or, equivalently, an orientation $F$ of the
incomparability graph of $P$) such that $P+F$ contains no forbidden
configurations for $\mathbf{2+2}$, $\mathbf{3+1}$, or $\mathbf{2+1}$.

###### Proof.

Let $\overline{G}$ be the incomparability graph of $P$. If $P$ is a linear-
semiorder, then Proposition 6 implies that there is an orientation $F$ of
$\overline{G}$ such that $P+F$ is acyclic and contains no forbidden
configurations for $\mathbf{2+2}$ or $\mathbf{3+1}$. Since $P+F$ is acyclic,
it contains no forbidden configurations for $\mathbf{2+1}$.

Suppose there is an orientation $F$ of $E_{o}$ such that $P+F$ contains no
forbidden configurations for $\mathbf{2+2}$, $\mathbf{3+1}$, or
$\mathbf{2+1}$. From Lemma 17, we have another orientation $F^{\prime}$ of
$E_{o}$ such that $P+F^{\prime}$ contains no forbidden configurations for
$\mathbf{2+2}$, $\mathbf{3+1}$, or $\mathbf{2+1}$, and $P+F^{\prime}$ contains
no obstructions. Since $P+F^{\prime}$ contains no obstructions, Lemma 13
implies that $P+F^{\prime}$ is acyclic. By Lemma 7, $P$ is a linear-semiorder.
∎

###### Proof of Theorem 5.

The first claim can be obtained from Theorem 18 and Lemma 10. The second claim
can be obtained from Lemmas 17, 13, 10 and 7. ∎

##  5\. Comparability invariance

A property of partial orders is called a _comparability invariant_ if either
all orders with the same comparability graph have that property or none has
that property. It is known that being a linear-interval order is a
comparability invariant [6]. In this section, we show the following.

######  Theorem 19.

Being a linear-semiorder is a comparability invariant.

From Theorems 19 and 5, we have the following.

######  Corollary 20.

Comparability graphs of linear-semiorders can be recognized in $O(n\bar{m})$
time, where $n$ and $\bar{m}$ are the number of vertices and non-edges of the
given graph, respectively. Incomparability graphs of linear-semiorders can be
recognized in $O(nm)$ time, where $m$ is the number of edges of the given
graph.

###### Proof.

We can recognize comparability graphs of linear-semiorders by the following
algorithm. Let $G$ be the given graph. First, obtain a transitive orientation
$P$ of $G$. If $G$ does not have a transitive orientation, $G$ is not a
comparability graph. Then, test whether $P$ is a linear-semiorder by
Algorithms 1–3. Theorem 19 ensures that every transitive orientation of $G$ is
a linear-semiorder if $G$ is the comparability graph of a linear-semiorder.
Thus the algorithm is correct. Both steps can be done in $O(n\bar{m})$ time as
shown in Proposition 1 and Theorem 5. Thus the algorithm takes $O(n\bar{m})$
time.

Since the complement of a graph can be obtained in $O(n^{2})$ time,
incomparability graphs of linear-semiorders can be recognized in $O(nm)$ time.
∎

To prove Theorem 19, we use the proof technique developed in [10]. Let $P$ be
a partial order on a set $V$. A non-empty subset $A\subseteq V$ is
_autonomous_ in $P$ if for any element $v\in V-A$, whenever $v\prec a$,
$v\parallel a$, or $v\succ a$ holds in $P$ for some element $a\in A$, then the
same holds for all elements $a\in A$. Let $P^{\prime}$ be a partial order with
the same comparability graph as $P$. The order $P^{\prime}$ is said to be
obtained from $P$ by a _reversal_ if there is an autonomous set $A$ of $P$
such that

  1. –

if not both of $u$ and $v$ are in $A$, then $u\prec v$ in $P^{\prime}$ if and
only if $u\prec v$ in $P$, and

  2. –

if both of $u$ and $v$ are in $A$, then $u\prec v$ in $P^{\prime}$ if and only
if $u\succ v$ in $P$.

We denote by $P\mid A$ the order obtained from $P$ by reversing $A$.

The following theorem provides a simple scheme to show the comparability
invariance.

######  Theorem 21 ([12]).

Two orders $P$ and $P^{\prime}$ have the same comparability graph if and only
if there is a finite sequence of orders $P_{0},P_{1},\ldots,P_{k}$ such that
$P_{0}=P$, $P_{k}=P^{\prime}$, and $P_{i}$ is obtained from $P_{i-1}$ by a
reversal for each $i=1,2,\ldots,k$.

Therefore, to prove Theorem 19, it suffices to show the following.

######  Lemma 22.

If an order $P$ on a set $V$ is a linear-semiorder and a subset $A\subseteq V$
is autonomous in $P$, then $P\mid A$ is a linear-semiorder.

###### Proof of Theorem 19.

Let $P$ and $P^{\prime}$ be two orders with the same comparability graph. It
suffices to show that $P$ is a linear-semiorder if and only if $P^{\prime}$ is
a linear-semiorder. From Theorem 21, there is a finite sequence of orders
$P=P_{0},P_{1},\ldots,P_{k}=P^{\prime}$ such that $P_{i}$ is obtained from
$P_{i-1}$ by a reversal for each $i=1,2,\ldots,k$. Suppose that $P=P_{0}$ is a
linear-semiorder. From Lemma 22, $P_{1}$ is also a linear-semiorder.
Continuing in this way, we have that $P_{k}=P^{\prime}$ is a linear-semiorder.
A symmetric argument would show that the converse also holds. ∎

In the rest of this section, we prove Lemma 22. Recall that $L_{1}$ and
$L_{2}$ are two horizontal lines in the $xy$-plane with $L_{1}$ above $L_{2}$.
As a representation of a linear-semiorder, we use a set of triangles between
$L_{1}$ and $L_{2}$ as follows.

Let $P$ be a linear-semiorder on a set $V$, and let $L$ and $S$ be a linear
order and a semiorder on $V$, respectively, with $L\cap S=P$. Let
$\\{p(v)\colon\ v\in V\\}$ be a set of points on $L_{1}$ such that $p(u)<p(v)$
if and only if $u\prec v$ in $L$ for any two elements $u,v\in V$. Note that
all the points are distinct. Let $\\{I(v)\colon\ v\in V\\}$ be a unit interval
representation of $S$ on $L_{2}$. We assume that no two intervals share a
common endpoint. Let $I(v)=[l(v),r(v)]$ for each element $v\in V$. Since each
interval has unit length, $l(v)+1=r(v)$.

Let $T(v)$ be the triangle spanned by $p(v)$ and $I(v)$. A triangle $T(u)$
_lies completely to the left of_ $T(v)$, and we write $T(u)\ll T(v)$, if
$p(u)<p(v)$ on $L_{1}$ and $I(u)\ll I(v)$ on $L_{2}$. We have that $u\prec v$
in $P$ if and only if $T(u)\ll T(v)$ for any two elements $u,v\in V$; hence we
call the set $\\{T(v)\colon\ v\in V\\}$ a _triangle representation_ of $P$.

Now, we fix a pair of a linear-semiorder $P$ and an autonomous set $A$ of $P$.
We also fix a triangle representation $\\{T(v)\colon\ v\in V\\}$ of $P$.

An element $a\in A$ is _isolated_ in $A$ if $a\parallel a^{\prime}$ in $P$ for
any element $a^{\prime}\in A-\\{a\\}$. Let $A^{*}$ be the subset of $A$
obtained by removing all isolated elements of $A$. We can observe the
following, and then we assume without loss of generality $A^{*}\neq\emptyset$.

######  Lemma 23.

The set $A^{*}$ is autonomous in $P$, and $P\mid A^{*}=P\mid A$.

We define that $l_{1}=\min_{v\in A^{*}}p(v)$ and $r_{1}=\max_{v\in
A^{*}}p(v)$, similarly, $l_{2}=\min_{v\in A^{*}}l(v)$ and $r_{2}=\max_{v\in
A^{*}}r(v)$. Let $C(A^{*})$ be the trapezoid spanned by the interval
$[l_{1},r_{1}]$ on $L_{1}$ and the interval $[l_{2},r_{2}]$ on $L_{2}$, while
$l_{1}$ is the upper-left corner of $C(A^{*})$ and $r_{1}$ is the upper-right
corner of $C(A^{*})$, similarly, $l_{2}$ is the lower-left corner of
$C(A^{*})$ and $r_{2}$ is the lower-right corner of $C(A^{*})$. Note that
$C(A^{*})$ can be viewed as the convex region spanned by the triangles $T(v)$
with $v\in A^{*}$. In addition, let $a_{l}^{1}$ and $a_{r}^{1}$ denote the
elements of $A^{*}$ with $p(a_{l}^{1})=l_{1}$ and $p(a_{r}^{1})=r_{1}$,
respectively. Similarly, let $a_{l}^{2}$ and $a_{r}^{2}$ denote the elements
of $A^{*}$ with $l(a_{l}^{2})=l_{2}$ and $r(a_{r}^{2})=r_{2}$, respectively.

Let $B$ be the set of elements $v\in V$ with $T(v)\subseteq C(A^{*})$.
Obviously, $B\supseteq A^{*}$. The convex region $C(B)$ spanned by the
triangles $T(v)$ with $v\in B$ is equal to $C(A^{*})$.

######  Lemma 24.

Let $v\in V-B$. If $T(v)\cap C(A^{*})\neq\emptyset$ then $T(v)$ intersects
with every triangle spanned by a point $p\in[l_{1},r_{1}]$ on $L_{1}$ and a
unit-length interval $I\subseteq[l_{2},r_{2}]$ on $L_{2}$.

###### Proof.

Since $v\notin B$, we have $T(v)\not\subseteq C(A^{*})$, and hence
$p(v)\notin[l_{1},r_{1}]$ or $I(v)\not\subseteq[l_{2},r_{2}]$.

Suppose $p(v)<l_{1}$. Since $T(v)\cap C(A^{*})\neq\emptyset$, we have
$l_{2}<r(v)$. Thus $T(v)\cap T(a_{l}^{2})\neq\emptyset$, and hence $v\parallel
a_{l}^{2}$ in $P$. Since $A^{*}$ is autonomous, $v\parallel a_{r}^{2}$ in $P$,
and hence $T(v)\cap T(a_{r}^{2})\neq\emptyset$. Thus $l(a_{r}^{2})<r(v)$.
Therefore, $p(v)<l_{1}$ and $l(a_{r}^{2})=r_{2}-1<r(v)$, and the claim holds.
A similar argument would show that the claim holds when $r_{1}<p(v)$.

Suppose $l(v)<l_{2}$. If $l_{2}<r(v)$ then $T(v)\cap
T(a_{l}^{2})\neq\emptyset$. If $r(v)<l_{2}$ then $T(v)\cap
C(A^{*})\neq\emptyset$ implies $l_{1}<p(v)$, and hence $T(v)\cap
T(a_{l}^{1})\neq\emptyset$. Thus in both cases, $v\parallel a$ in $P$ for some
element $a\in A^{*}$. Since $A^{*}$ is autonomous, $v\parallel a_{r}^{1}$ in
$P$. Since $a_{r}^{1}$ is not isolated, there is an element $a^{\prime}\in
A^{*}$ with $T(a^{\prime})\ll T(a_{r}^{1})$. Since $l(v)<l_{2}\leq
l(a^{\prime})$ and each interval has unit length, $r(v)<r(a^{\prime})$, and
hence $I(v)\ll I(a_{r}^{1})$. It follows $p(a_{r}^{1})<p(v)$. Therefore,
$r_{1}<p(v)$ and $l(v)<l_{2}$, and the claim holds. A similar argument would
show that the claim holds when $r_{2}<r(v)$. ∎

From Lemma 24, we have the following.

######  Lemma 25.

For any element $v\in V-B$, one of the following holds:

  1. –

$T(v)$ lies completely to the left of $C(A^{*})$.

  2. –

$T(v)$ intersects with every triangle contained in $C(A^{*})$.

  3. –

$T(v)$ lies completely to the right of $C(A^{*})$.

We also have the following from Lemma 25

######  Lemma 26.

The set $B$ is autonomous in $P$.

###### Proof.

Let $v\in V-B$. Suppose that $v\parallel b$ in $P$ for some element $b\in B$.
Then $T(v)\cap T(b)\neq\emptyset$ implies $T(v)\cap C(A^{*})\neq\emptyset$,
and hence $T(v)\cap T(b)\neq\emptyset$ for all elements $b\in B$. Thus
$v\parallel b$ in $P$ for all elements $b\in B$. If $v\prec b$ in $P$ for some
element $b\in B$, then $T(v)$ lies completely to the left of $C(A^{*})$, and
hence $v\prec b$ in $P$ for all elements $b\in B$. If $v\succ b$ in $P$ for
some element $b\in B$, then $T(v)$ lies completely to the right of $C(A^{*})$,
and hence $v\succ b$ in $P$ for all elements $b\in B$. ∎

Let $P_{1}=P\mid B$. We define $\\{T^{\prime}(v)\colon\ v\in V\\}$ as the set
of triangles obtained from $\\{T(v)\colon\ v\in V\\}$ by _flipping the
representation of $B$ relative to $C(B)$_, that is, $T^{\prime}(v)=T(v)$ for
any element $v\in V-B$ whereas for each element $v\in B$, the triangle
$T^{\prime}(v)$ is the triangle spanned by the point $l_{1}+r_{1}-p(v)$ on
$L_{1}$ and the interval $[l_{2}+r_{2}-r(v),l_{2}+r_{2}-l(v)]$ on $L_{2}$.
Note that the convex region $C^{\prime}(B)$ spanned by the triangles
$T^{\prime}(v)$ with $v\in B$ is equal to $C(B)$.

######  Lemma 27.

The order $P_{1}$ is a linear-semiorder with a representation
$\\{T^{\prime}(v)\colon\ v\in V\\}$.

###### Proof.

Let $P^{\prime}$ be the partial order on $V$ defined by
$\\{T^{\prime}(v)\colon\ v\in V\\}$, and let $u$ and $v$ be two elements of
$V$. If neither $u$ nor $v$ is in $B$, then their relation in $P^{\prime}$
remains the same as in $P$. If either $u$ or $v$ is in $B$, then Lemma 25
ensures that their relation in $P^{\prime}$ remains the same as in $P$. If
both $u$ and $v$ are in $B$, then $T^{\prime}(u)\ll T^{\prime}(v)\iff T(u)\gg
T(v)$; hence $u\prec v$ in $P^{\prime}$ if and only if $u\succ v$ in $P$. Thus
$P^{\prime}=P_{1}$. ∎

Let $A_{1}=B-A^{*}$. If $A_{1}=\emptyset$ then $B=A^{*}$, and hence $P\mid
A=P\mid A^{*}=P\mid B=P_{1}$ is a linear-semiorder. Thus we assume without
loss of generality $A_{1}\neq\emptyset$.

######  Lemma 28.

All elements of $A_{1}$ are incomparable to all elements of $A^{*}$ in $P$.

###### Proof.

Suppose there is an element $a\in A_{1}$ with $a\prec a^{\prime}$ in $P$ for
some element $a^{\prime}\in A^{*}$. Since $A^{*}$ is autonomous, $a\prec
a_{l}^{1}$ and $a\prec a_{l}^{2}$ in $P$, contradicting $T(a)\cap
C(A^{*})\neq\emptyset$. Similarly, there are no elements $a\in A_{1}$ with
$a^{\prime}\prec a$ in $P$ for some element $a^{\prime}\in A^{*}$. ∎

######  Lemma 29.

The set $A_{1}$ is autonomous in $P_{1}$, and $P_{1}\mid A_{1}=P\mid A$.

###### Proof.

Let $v\in V-A_{1}$. If $v\in V-B$ then, since $B$ is autonomous in $P_{1}$,
whenever $v\prec a$, $v\parallel a$, or $v\succ a$ holds in $P_{1}$ for some
element $a\in A_{1}\subseteq B$, the same holds for all elements $a\in A_{1}$.
If $v\in B-A_{1}$ then $v\in A^{*}$, and we have from Lemma 28 that
$v\parallel a$ in $P_{1}$ for all elements $a\in A_{1}$. Thus $A_{1}$ is
autonomous in $P_{1}$.

Lemma 28 implies $P\mid B=(P\mid A^{*})\mid A_{1}$. Thus $(P\mid B)\mid
A_{1}=P\mid A^{*}$. Since $P_{1}=P\mid B$ and $P\mid A^{*}=P\mid A$, we have
$P_{1}\mid A_{1}=P\mid A$. ∎

We repeat the process by replacing $P$ and $A$ with $P_{1}$ and $A_{1}$,
respectively. Let $A_{1}^{*}$ be the subset of $A_{1}$ obtained by removing
all isolated elements of $A_{1}$. From Lemma 23, the set $A_{1}^{*}$ is
autonomous in $P_{1}$ and $P_{1}\mid A_{1}^{*}=P_{1}\mid A_{1}$. We assume
without loss of generality $A_{1}^{*}\neq\emptyset$. We define
$C^{\prime}(A_{1}^{*})$ as the convex region spanned by the triangles
$T^{\prime}(v)$ with $v\in A_{1}^{*}$. Let $B_{1}$ be the set of elements
$v\in V$ with $T^{\prime}(v)\subseteq C^{\prime}(A_{1}^{*})$. From Lemma 26,
the set $B_{1}$ is autonomous in $P_{1}$, and let $P_{2}=P_{1}\mid B_{1}$.
From Lemma 27, the order $P_{2}$ is a linear-semiorder. Let
$A_{2}=B_{1}-A_{1}^{*}$, and we assume without loss of generality
$A_{2}\neq\emptyset$. From Lemma 29, the set $A_{2}$ is autonomous in $P_{2}$,
and $P_{2}\mid A_{2}=P_{1}\mid A_{1}$.

Let $A_{2}^{*}$ be the subset of $A_{2}$ obtained by removing all isolated
elements of $A_{2}$. From Lemma 23, the set $A_{2}^{*}$ is autonomous in
$P_{2}$, and $P_{2}\mid A_{2}^{*}=P_{2}\mid A_{2}$.

######  Lemma 30.

The set $A_{2}^{*}$ is a proper subset of $A^{*}$.

###### Proof.

Since $A_{1}^{*}\subseteq B$, we have $C^{\prime}(A_{1}^{*})\subseteq
C^{\prime}(B)=C(B)=C(A^{*})$. Thus $B_{1}\subseteq B$. Suppose $a_{l}^{1}\in
B_{1}$. Then $T^{\prime}(a_{l}^{1})\subseteq C^{\prime}(A_{1}^{*})$. Since
$a_{l}^{1}\in A^{*}$, we have $a_{l}^{1}\notin A_{1}^{*}=B-A^{*}$. Thus there
are two elements $a,b\in A_{1}^{*}$ with
$p^{\prime}(a)<p^{\prime}(a_{l}^{1})<p^{\prime}(b)$, where $p^{\prime}(v)$ is
the point of $T^{\prime}(v)$ on $L_{1}$. However,
$p^{\prime}(a_{l}^{1})=l_{1}+r_{1}-p(a_{l}^{1})=r_{1}$, that is,
$r_{1}<p^{\prime}(b)$, contradicting $C^{\prime}(A_{1}^{*})\subseteq
C(A^{*})$. Therefore, $a_{l}^{1}\notin B_{1}$.

The set $B$ can be partitioned into three sets $A^{*}$, $A_{1}-A_{1}^{*}$, and
$A_{1}^{*}$. By definition, all elements of $A_{1}-A_{1}^{*}$ are incomparable
to all other elements of $A_{1}$. From Lemma 28, all elements of
$A_{1}-A_{1}^{*}$ are incomparable to all elements of $A^{*}$. Thus all
elements of $A_{1}-A_{1}^{*}$ are incomparable to all other elements of $B$.

We have $A_{2}^{*}\subseteq A_{2}=B_{1}-A_{1}^{*}\subseteq
B-A_{1}^{*}=A^{*}\cup(A_{1}-A_{1}^{*})$. Since all elements of
$A_{1}-A_{1}^{*}$ are incomparable to all elements of $A_{2}\subseteq B$, we
have $A_{2}^{*}\cap(A_{1}-A_{1}^{*})=\emptyset$. Thus $A_{2}^{*}\subseteq
A^{*}$. Since $a_{l}^{1}\in A^{*}$ but $a_{l}^{1}\notin B_{1}\supseteq
A_{2}^{*}$, the inclusion is proper. ∎

Now, we prove Lemma 22.

###### Proof of Lemma 22.

Suppose that the lemma does not hold. Then there is a pair of a linear-
semiorder $P$ and an autonomous set $A$ of $P$ such that $P\mid A$ is not a
linear-semiorder. Among such pairs, we choose one with minimal $|A|$. Lemma 29
implies $P\mid A=P_{1}\mid A_{1}=P_{2}\mid A_{2}=P_{2}\mid A_{2}^{*}$, but
Lemma 30 implies $|A_{2}^{*}|<|A^{*}|\leq|A|$, contradicting the minimality of
$A$. ∎

##  6\. Miscellaneous

We finally show two byproducts of Theorem 2.

###  6.1. Vertex ordering characterization

Let $G=(V,E)$ be a graph. A _vertex ordering_ of $G$ is a linear order on $V$.
A _vertex ordering characterization_ of a graph class $\mathcal{C}$ is a
characterization of the following type: a graph $G$ is in $\mathcal{C}$ if and
only if $G$ has a vertex ordering fulfilling some properties. For example, a
graph $G$ is the incomparability graph of an order if and only if there is a
vertex ordering $L$ of $G$ such that for any three vertices $u,v,w$ of $G$
with $u\prec v\prec w$ in $L$, if $uw\in E$ then $uv\in E$ or $vw\in E$ [16].
Equivalently, a graph is the incomparability graph of an order if and only if
it has a vertex ordering that contains no suborderings in Fig. 1212(a).

Incomparability graphs of linear-interval orders can be characterized so that
a graph $G$ is the incomparability graph of a linear-interval order if and
only if there is a vertex ordering of $G$ that contains no suborderings in
Figs. 1212(a)–12(c) [25]. Moreover, a vertex ordering of $G$ that contains no
suborderings in Figs. 1212(a)–12(c) can be obtained in $O(nm)$ time [26],
where $n$ and $m$ are the number of vertices and edges of $G$, respectively.
For linear-semiorders, the following can be obtained from Theorems 2 and 5.

######  Corollary 31.

A graph $G$ is the incomparability graph of a linear-semiorder if and only if
there is a vertex ordering of $G$ that contains no suborderings in Figs.
1212(a)–12(e). A vertex ordering of a graph $G$ that contains no suborderings
in Figs. 1212(a)–12(e) can be computed in $O(m^{2}\bar{m})$ time if $G$ is the
incomparability graph of a linear-semiorder. Here, $m$ and $\bar{m}$ are the
number of edges and non-edges of $G$, respectively.

$u$$v$$x$ (a) $u$$v$$w$$x$ (b) $u$$v$$w$$x$ (c)

$u$$v$$w$$x$ (d) $u$$v$$w$$x$ (e)

Figure 12.  Forbidden patterns in vertex orderings where $u\prec v\prec w\prec
x$. Lines and dashed lines denote edges and non-edges, respectively. Edges
that may or may not be present is not drawn.

###### Proof.

Assume there is a linear-semiorder $P$ on a set $V$ such that the
incomparability graph of $P$ is $G$. Then $P$ has a linear extension $L$
fulfilling the $\mathbf{2+2}$ and $\mathbf{3+1}$ rules. Notice that $L$ can be
viewed as a vertex ordering of $G$. Since $L$ is a linear extension of a
partial order, it has no suborderings in Fig. 1212(a). Since $L$ has no
forbidden configurations for $\mathbf{2+2}$, it has no suborderings in Figs.
1212(b) and 1212(c). Since $L$ has no forbidden configurations for
$\mathbf{3+1}$, it has no suborderings in Figs. 1212(d) and 1212(e).

Conversely, assume there is a vertex ordering $L$ of $G=(V,E)$ with no
suborderings in Figs. 1212(a)–12(e). Let $P$ be a binary relation on $V$ such
that $(u,v)\in P$ if and only if $uv\notin E$ and $u\prec v$ in $L$ for any
two elements $u,v\in V$. Since $L$ has no suborderings in Fig. 1212(a), the
relation $P$ is transitive, and hence a partial order. Then $L$ can be viewed
as a linear extension of $P$. Since $L$ has no suborderings in Figs. 1212(b)
and 1212(c), it has no forbidden configurations for $\mathbf{2+2}$. Since $L$
has no suborderings in Figs. 1212(d) and 1212(e), it has no forbidden
configurations for $\mathbf{3+1}$. Therefore, Theorem 2 implies that $P$ is a
linear-semiorder. Since $G$ is the incomparability graph of $P$, we have the
first claim.

Let $G$ be the incomparability graph of a linear-semiorder. We can compute the
vertex ordering of $G$ by the following algorithm. First, take a complement
$\overline{G}$ of $G$. Then, obtain a transitive orientation $P$ of
$\overline{G}$. Finally, compute a linear extension $L$ of $P$ fulfilling the
$\mathbf{2+2}$ and $\mathbf{3+1}$ rules. As mentioned above, $L$ can be viewed
as a vertex ordering of $G$ with no suborderings in Figs. 1212(a)–12(e). Thus
the algorithm is correct. The first step can be done in $O(n^{2})$ time. The
second and third steps can be done in $O(nm)$ time and $O(m^{2}\bar{m})$ time,
respectively, as shown in Proposition 1 and Theorem 5. Thus the algorithm
takes $O(m^{2}\bar{m})$ time. ∎

###  6.2. Linear-semiorders and interval orders

The class of linear-interval orders contains interval orders and orders of
dimension 2 as proper subclasses [8]. The following example shows that the
class of interval orders is not a subclass of linear-semiorders.

######  Example 32.

The interval order $P_{I}$ in Fig. 1313(a) is not a linear-semiorder.

###### Proof.

Figure 1313(b) shows an interval representation of $P_{I}$. Suppose that
$P_{I}$ is a linear-semiorder. Then Theorem 2 implies that $P_{I}$ has a
linear extension $L$ fulfilling the $\mathbf{3+1}$ rule.

The order $\mathbf{3+1}$ consisting of $b_{1},b_{2},b_{3},a_{1}$ requires that
$a_{1}\prec b_{1}$ in $L$ if and only if $a_{1}\prec b_{3}$ in $L$. The order
$\mathbf{3+1}$ consisting of $a_{1},a_{2},a_{3},b_{3}$ requires that
$a_{1}\prec b_{3}$ in $L$ if and only if $a_{3}\prec b_{3}$ in $L$. The order
$\mathbf{3+1}$ consisting of $b_{3},b_{4},b_{5},a_{3}$ requires that
$a_{3}\prec b_{3}$ in $L$ if and only if $a_{3}\prec b_{5}$ in $L$. Thus
$a_{1}\prec b_{1}$ in $L$ if and only if $a_{3}\prec b_{5}$ in $L$.

The order $\mathbf{3+1}$ consisting of $b_{1},b_{2},c_{2},a_{1}$ requires that
$a_{1}\prec b_{1}$ in $L$ if and only if $a_{1}\prec c_{2}$ in $L$. The order
$\mathbf{3+1}$ consisting of $a_{1},b_{4},b_{5},c_{2}$ requires that
$a_{1}\prec c_{2}$ in $L$ if and only if $b_{5}\prec c_{2}$ in $L$. The order
$\mathbf{3+1}$ consisting of $c_{1},b_{4},b_{5},c_{2}$ requires that
$b_{5}\prec c_{2}$ in $L$ if and only if $c_{1}\prec c_{2}$ in $L$. Thus
$a_{1}\prec b_{1}$ in $L$ if and only if $c_{1}\prec c_{2}$ in $L$.

Similarly, the order $\mathbf{3+1}$ consisting of $c_{1},b_{4},b_{5},a_{3}$
requires that $a_{3}\prec b_{5}$ in $L$ if and only if $a_{3}\prec c_{1}$ in
$L$. The order $\mathbf{3+1}$ consisting of $b_{1},b_{2},a_{3},c_{1}$ requires
that $a_{3}\prec c_{1}$ in $L$ if and only if $b_{1}\prec c_{1}$ in $L$. The
order $\mathbf{3+1}$ consisting of $b_{1},b_{2},c_{2},c_{1}$ requires that
$b_{1}\prec c_{1}$ in $L$ if and only if $c_{2}\prec c_{1}$ in $L$. Thus
$a_{3}\prec b_{5}$ in $L$ if and only if $c_{2}\prec c_{1}$ in $L$, a
contradiction. Therefore, $P_{I}$ has no linear extensions fulfilling the
$\mathbf{3+1}$ rule, that is, $P_{I}$ is not a linear-semiorder. ∎

$a_{1}$$a_{2}$$a_{3}$$b_{1}$$b_{2}$$b_{3}$$b_{4}$$b_{5}$$c_{1}$$c_{2}$ (a)
$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$11$$12$$13$$a_{1}$$a_{2}$$a_{3}$$b_{1}$$b_{2}$$b_{3}$$b_{4}$$b_{5}$$c_{1}$$c_{2}$
(b)

Figure 13.  (a) An interval order $P_{I}$ that is a minimal forbidden order of
linear-semiorders. (b) An interval representation of $P_{I}$.

Note that one can check by inspection that every proper induced suborder of
$P_{I}$ has a linear extension fulfilling the $\mathbf{3+1}$ rule. Since
$P_{I}$ is an interval order, $P_{I}$ and every its induced suborder do not
contain $\mathbf{2+2}$ as an induced suborder [11]. Hence every proper induced
suborder of $P_{I}$ is a linear-semiorder, that is, $P_{I}$ is a minimal
forbidden order of linear-semiorders.

######  Corollary 33.

The class of linear-semiorders is not a subclass of interval orders and vice
versa; therefore, the class of linear-semiorders is a proper subclass of
linear-interval orders. The class of linear-semiorders contains semiorders and
orders of dimension 2 as proper subclasses.

###### Proof.

Example 32 shows an interval order (hence a linear-interval order) that is not
a linear-semiorder. The order $\mathbf{2+2}$ is a linear-semiorder but is not
an interval order.

From definitions, every semiorder and order of dimension 2 is a linear-
semiorder. Thus the classes of semiorders and orders of dimension 2 are
subclasses of linear-semiorders. Since the linear-semiorder in Fig. 1 is
neither a semiorder (since it contains $\mathbf{2+2}$ as an induced suborder)
nor an order of dimension 2 [28], the inclusion is proper. ∎

##  7\. Concluding remarks

In this paper, we introduce linear-semiorders and show a characterization and
a polynomial-time recognition algorithm for this new order class. We also
prove that being a linear-semiorder is a comparability invariant, showing that
incomparability graphs of linear-semiorders can also be recognized in
polynomial time. As byproducts, we show a vertex ordering characterization of
incomparability graphs of linear-semiorders and inclusion relationships
between the order classes.

We finally list some open problems on linear-semiorders.

  1. –

Our algorithm takes $O(n\bar{m})$ time to recognize linear-semiorders and
takes $O(m\bar{m}^{2})$ time to produce a linear extension fulfilling the
$\mathbf{2+2}$ and $\mathbf{3+1}$ rules, where $n$, $m$, and $\bar{m}$ are the
number of elements, comparable pairs, and incomparable pairs of the given
order, respectively. Is there any faster or simpler algorithm for recognizing
linear-semiorders?

  2. –

The class of linear-semiorders is closed under taking induced suborders. Hence
the orders can be characterized by forbidden induced suborders. Can we obtain
the list of forbidden induced suborders for linear-semiorders?

  3. –

The isomorphism problem can be solved in linear time for interval graphs [17]
and permutation graphs [7], whereas the complexity of the problem remains open
for incomparability graphs of linear-interval orders [24, 27, 29]. For
incomparability graphs of linear-semiorders, can we determine the complexity
of the isomorphism problem?

#### Acknowledgments

We are grateful to the anonymous referees of the preliminary version of this
paper for their time and valuable suggestions. A part of this work was done