{'fraction_non_alphanumeric': 0.05379296169600517, 'fraction_numerical': 0.01071748418069972, 'mean_word_length': 3.4835439705107953, 'pattern_counts': {'":': 0, '<': 70, '<?xml version=': 0, '>': 17, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 34, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Recognizing (Unit) Interval Graphs by Zigzag Graph Searches

Corneil, Olariu, and Stewart [SODA 1998; SIAM Journal on Discrete Mathematics 2009] presented a recognition algorithm for interval graphs by six graph searches. Li and Wu [Discrete Mathematics \&Theoretical Computer Science 2014] simplified it to only four. The great simplicity of the latter algorithm is however eclipsed by the complicated and long proofs. The main purpose of this paper is to present a new and significantly short proof for Li and Wu's algorithm, as well as a simpler implementation. We also give a self-contained simpler interpretation of the recognition algorithm of Corneil [Discrete Applied Mathematics 2004] for unit interval graphs, based on three sweeps of graph searches. Moreover, we show that two sweeps are already sufficient. Toward the proofs of the main results, we make several new structural observations that might be of independent interests.


Introduction
If we take the 26 monarchy rulers of China, France, and United Kingdom (England and Scotland before 1707) during the period between 1661 and 1900, mark their reigns in the timeline, and make a graph to indicate the intersection relationships between their reigns, we end with the graph in Figure 1. Formally, a graph is an interval graph if its vertices can be assigned to intervals on the real line such that there is an edge between two vertices if and only if their corresponding intervals intersect. As in the opening example, interval graphs can be used to represent, among others, relations of a temporal nature. Although it is very easy to draw a graph out of a set of intervals, the other direction, reconstructing an interval representation from a given interval graph, is a challenging task. Indeed, it is already very nontrivial to decide whether a graph is an interval graph or not. For example, it is not that obvious why the graph in Figure 1 is an interval graph from the graph itself, without the background information. Let us briefly relate the history of recognition algorithms for interval graphs. Throughout we use n to denote the number of vertices in the input graph. An interval graph has at most n maximal cliques, and Fulkerson and Gross [11] observed that they can be arranged in a linear manner, called a clique path, such that every vertex is contained in a consecutive set of them. For example, the graph in Figure 2 has five maximal cliques, which correspond to the five integers in the representation: In particular, the ith clique comprises vertices whose intervals containing point i. All the maximal cliques of an interval graph can be found in linear time [24]. (We know the answer is "no" if more than n maximal cliques were found.) Earlier recognition algorithms for interval graphs tried to orient the maximal cliques. A naïve implementation would take O(n 3 ) time. Booth and Lueker [1] invented a complicated data structure to capture the ordering of the maximal cliques, and showed how to use this data structure to recognize interval graphs in linear time. Their approach was simplified by Korte and Möhring [17] and Hsu and McConnell [16]. Another natural approach is to start from a clique tree of the input graph, defined similarly as a clique path and can be constructed in linear time [24], and try to transform it into a path. Both Hsu and Ma [15] and Habib et al. [13] took this approach. All the aforementioned algorithms are indirect, in the sense that they first check whether the input graph is chordal-a graph is chordal if every induced cycle in it is a triangle-and continue only when the answer is yes. Since any induced cycle longer than three cannot have an interval representation, all interval graphs are chordal. Rose et al. [24] has developed a linear-time algorithm to decide whether a graph is chordal, and if yes, a clique tree can be built in the same time. These maximal cliques are the starting point of aforementioned algorithms. Since the structures of interval graphs are simpler than those of chordal graphs, one may consider the indirect approaches counterintuitive in a sense.
The algorithm of Rose et al. [24] is based on a refined version of breadth-first search, called lexicographical breadth-first search (LBFS for short). The output of LBFS is an ordering of the vertices, which satisfies certain property if and only if the graph is chordal. Interestingly, the algorithms of Hsu and Ma [15] and Habib et al. [13] heavily rely on LBFS. Since a linear ordering of vertices is more perspicuous in interval graphs than in chordal graphs, it seems natural to also take the ordering approach to design a direct recognition algorithm for interval graphs. Given an interval representation for an interval graph G, if we sort all the vertices by the left endpoints of their intervals in the representation, then for any three vertices in order, the adjacency of the first and the third vertices would force the adjacency of the first two vertices; see, e.g., the ordering 1, 2, . . . , 8 for the graph in Figure 2. It turns out that a graph G is an interval graph if and only if G admit an ordering with the this property [22], hence called an interval ordering.
Since every interval ordering is an LBFS ordering, it seems very natural to use LBFS to produce an interval ordering of the input graph. On the other hand, an LBFS ordering of an interval graph can be completely different from an interval ordering. A necessary condition for an LBFS ordering to be an interval ordering is that it needs to start from certain vertices. Simon [25] was probably the first who tried this approach. After an initial LBFS, he conducted multiple sweeps of a variation of LBFS, called LBFS + , each of which uses the outcome of the previous one to help break ties; in particular, it starts from the last vertex of the previous sweep. Although fatally flawed, Simon's algorithm inspired fruitful exploration in this direction. (According to [8], Ma also made similar attempts.) The real breakthrough was made by Corneil et al. [8], who observed that LBFS and LBFS + may not be sufficient, and proposed one more variation of LBFS. The development of this algorithm was not smooth: The four-sweep algorithm claimed in the conference version [7], titled The ultimate interval graph recognition algorithm?, turned out to be over-optimistic. After significant reworking, they managed to make an algorithm that conducts six sweeps of LBFS and variations, of which the last sweep is very complicated.
Li and Wu [19] greatly simplified the algorithm of Corneil et al. [8]. They devised yet another variation of LBFS to catch the key concept of Corneil et al. [8]. Although their algorithm is greatly simple, the argument is excruciatingly complicated. Even experts in interval graphs sometimes find difficulty in following the sequence of 32 propositions, with almost no explanation in between. The main purpose of this paper is thus to give a short proof for this algorithm, with only cosmetic modifications to the algorithm itself.
An important subclass of interval graphs are unit interval graphs, those having interval representations in which all the intervals have the same length. (Image a remote planet, where the president of each nation serves a six-year term, with no possibility of re-election. Then the tenures of all the presidents form a unit interval graph.) Unit interval graphs are also well studied, and there have been several recognition algorithms proposed in literature. We also include a self-contained presentation of the recognition algorithm of Corneil [4] for unit interval graphs, and our purpose is twofold. First, we present both algorithms with a similar core idea, and thus the algorithm for unit interval graphs can be a warm-up of the main algorithm we are going to present. 1 An oversimplistic summary of the algorithms for unit interval graphs and interval graphs is that they work by breaking, respectively, fake twins and fake modules. Although the full details of the main result of this paper can be understood with Section 3 skipped, we strongly suggest the reader to take this detour. Second, compared to the algorithm that is simple enough for a freshman, the analysis of the original paper [4] heavily relies on previous work. Thus, a self-contained presentation might be worthwhile for its own. (We have to, nevertheless, resist this attempt to give a self-contained presentation for Li and Wu's algorithm, because it would make the paper too long. Since procedure LBFS + is well studied and well understood, we will cite results on them from literature, while proving everything else in the paper.) During the presentation of the algorithms, we prove several new lemmas; as far as I can check, they have not been explicitly stated in literature. Although none of the new lemmas can be called major, they do simplify and streamline a lot of important results. For example, our characterizations of all (unit) interval orderings imply a simple two-sweep recognize algorithm for unit interval graphs. We also prove the uniqueness of unit interval ordering of unit interval graphs with no true twins, discovered by Deng et al. [9], and the uniqueness of clique paths of interval graphs with no nontrivial modules, discovered by Hsu [14]. We hope our new observations can shed more light on the algorithms and on (unit) interval graphs in general.
As a final remark, the success of conducting multiple runs of LBFS to recognize (unit) interval graphs had inspired a series of algorithms based on a similar approach. We refer the interested reader to the survey of Corneil [3].

Preliminaries
All graphs discussed in this paper are undirected and simple. The vertex set and edge set of a graph G are denoted by, respectively, V(G) and clique is a set of pairwise adjacent vertices, and a clique is maximal if it is not proper subset of another clique. A graph G is complete if V(G) is a clique. We say that a vertex v is simplicial if N[v] is a clique; such a clique is necessarily maximal.
A set of intervals representing an interval graph G is called an interval representation for G, where the interval for vertex v is I(v). In this paper, all intervals are closed. An example is given in Figure 2. (Most authors would also require every interval to have a positive length. However, it is more convenient for us to allow zero-length intervals.) If for each of n (not necessarily distinct) left endpoints of the n intervals, we take the set of vertices whose intervals contain this point, then we end with n cliques. We leave it to the reader to verify that they include all the maximal cliques of G. If we list the distinct maximal cliques from left to right, sorted by the endpoints that we use to define these cliques, then we can see that for any v ∈ V(G), the maximal cliques containing v appear consecutively. We say that such a linear arrangement of maximal cliques a clique path of G. On the other hand, given a clique path K 1 , K 2 , . . . , K for an interval graph G with maximal cliques, for each vertex v we can define an interval [lp(v), rp(v)], where lp(v) and rp(v) are the indices of the first and, respectively, last maximal cliques containing v. One may easily see that they define an interval representation for G; see, e.g., Figure 2. Therefore, a graph G is an interval graph if and only if G has a clique path. As a consequence of this construction, every interval graph admits an interval representation in which all the endpoints are integers between 1 and n. One may note that an interval I(v) obtained in this way has length zero if and only if v is simplicial.
Yet another characterization of interval graphs is through vertex orderings. An ordering σ of the vertex set of a graph G is a bijection from V(G) → {1, . . . , n}. If we scan the intervals in a given interval representation by their left endpoints, in non-decreasing order, we obtain an ordering of the vertices. Without loss of generality, let it be v 1 , v 2 , . . ., v n . If for some i and k with 1 i < k n, vertices v i and v k are adjacent, then the right endpoint of I(v i ) is larger than the left endpoint of I(v k ). By the ordering, for every j with i < j < k, the left endpoint of I(v j ) is contained in I(v i ). In other words, for any triple of integers i, j, k with 1 i < j < k n, if v i v k ∈ E(G) then v i v j ∈ E(G) as well. An ordering of V(G) having this property is called an interval ordering of G [22]. On the other hand, it is also easy to derive an interval representation from an interval ordering σ, by setting where v j is the last neighbor of v i in σ. Therefore, interval representations, clique paths, and interval orderings (equipped with the index of the last neighbor of each vertex) are essentially equivalent, and they can be transformed into each other without explicitly building the graph. The direct transformation between a clique path and an interval ordering, to be introduced in Section 4, will be used to argue the correctness of the algorithm. However, one should be careful that both interval representations and clique paths have reflection symmetry, while the reversal of an interval ordering is not an interval ordering in general. The interval ordering corresponding to the mirror image of an interval representation is the ordering of right endpoints, in non-increasing order; e.g., 2, 8, 6, 7, 4, 5, 3, 1 for the graph in Figure 2.
Given an ordering σ of V(G), we can verify whether σ is an interval ordering in linear time as follows. First, we renumber the vertices such that σ(v i ) = i. Second, sort the adjacency list for each vertex in the decreasing order. 2 For example, if G is the graph in Figure 2, and σ = 1, 2, . . . , 8 , then the lists are [2]; [8, 7, and [2]. To finish the task, it suffices to check for all i = 1, . . . , n − 1, the ith list starts from If G is not an interval graph, then no ordering of V(G) can be an interval ordering. Thus, any ordering of V(G) will fail our test. For our purpose, therefore, it suffices to develop a procedure that finds an interval ordering if given an interval graph. In our presentation we will focus on the behavior of the procedure on an interval graph.
Breadth-first search (BFS) is arguably the simplest graph algorithm, and a backbone version, for a connected graph, can be described as follows.
• Initialize a queue whose only element is a starting vertex of the graph.
• While the queue is nonempty, dequeue a vertex v from the queue, and enqueue all the neighbors of v that have not already been visited (i.e., enqueued by earlier steps).
In BFS, there is no specific order on visiting the unvisited neighbors of v. In the very extreme case, the starting vertex is universal, i.e., adjacent to all other vertices, and the other vertices can be visited in any order. (The standard output of BFS is a tree representing the discovery relation, in which the order of siblings is immaterial.) Since we look for an ordering of the vertices, we may want a more refined control on the algorithm. Whenever there is a set S of vertices to be visited, we may conduct a BFS of the subgraph G[S] and visit them in order. If we impose this restriction recursively, then we end with lexicographic breadth-first search (LBFS). To see the difference between BFS and LBFS, let us consider the graph in Figure 2. In a BFS from vertex 1, vertices 3 through 8 can be in any order, where no LBFS of the graph can end with vertex 4, 5, or 6. It is worth noting that an LBFS can still have ties, which we break arbitrarily. The name LBFS comes from the following more standard description in Figure 3. 3 Let L 1 and L 2 be two different subsets of {1, 2, . . . , n}. We say that L 1 is lexicographically larger than L 2 if 2 As a standard algorithm exercise, this can be done without calling any sorting algorithm. For example, we create n new linked lists, each for a vertex, and all initially empty. Then for i = 1, . . . , n, we scan the neighbors of v i , and add i to the lists corresponding to neighbors of v i . After all the n vertices are scanned, the n lists contain the information we desire. Recall that the insertion to a linked list is done at the front. 3 Our definition of lexicographic ordering is slightly unnatural. As explained in the next paragraph, the original the minimum element in (L 1 \ L 2 ) ∪ (L 2 \ L 1 ) belongs to L 1 ; e.g., {1, 2} is lexicographically larger than both {1} and {1, 3, 4}.
S ← unvisited vertices with the lexicographically largest label; 2.2.
v ← any vertex in S; for each unvisited neighbor of v do add i to label(v); 3. return σ. Proof. We may assume without loss of generality that σ(v i ) = i for all i = 1, . . . , n. For any three numbers i, p, and q with i , and after visiting {v 1 , . . . , v p−1 }, the label of v p is no smaller than that of v q for any q > p.
Rose et al. [24] devised LBFS for the purpose of recognizing chordal graphs. They showed that the last vertex of an LBFS ordering σ of a chordal graph G is always simplicial. In an LBFS, the decision on which vertex to visit next solely depends on the visited ones, and thus for i = 1, . . . , n, the sub-ordering of the first i vertices in σ is an LBFS ordering of the subgraph induced by these vertices. Therefore, if we remove vertices in the reversal order of the LBFS ordering of a chordal graph, then every vertex is simplicial at the moment it is removed. Such an ordering of removing vertices is called a perfect elimination ordering, and it exists if and only if the graph is chordal [10]. We use u < σ v to denote that σ(u) < σ(v). A sub-ordering of an ordering σ restricted to S ⊆ V(G), denoted by σ| S , is the ordering from S → {1, . . . , |S|} such that u < σ| S v if and only if u < σ v for all u, v ∈ S. Note that a simplicial vertex v of a graph G is simplicial in G[U] for any U containing v.
Theorem 2.2 (The perfect elimination theorem [24]). Let G be a chordal graph, and let σ be an LBFS ordering of G. For any subset S ⊆ V(G), the last vertex of σ| S is simplicial in G[S].
We say that a vertex v of a graph G is an (LBFS) end vertex of G if there exists an LBFS ordering σ of G such that σ(v) = n. The key observation in [24] can be restated as that all end vertices of a chordal graph G are simplicial in G. The other direction of the perfect elimination theorem is not true in general; e.g., vertex 5 in Figure 2 is simplicial but cannot be the last vertex of any LBFS ordering of the graph. The original success of LBFS thus crucially hinges on the end vertices. On an interval graph G, a stronger property of end vertices was observed by Simon [25,Lemma 16]. This property is also implicit in [8], and another proof for it can be found in [19,Corollary 4.23].
purpose of using LBFS was to find a perfect elimination ordering for a chordal graph. In that setting, the labels in an LBFS are assigned from n to 1, instead of 1 to n as ours. Also note that some authors present LBFS with a specific starting vertex, similar as BFS above. We omit it because it is not necessary. [25,19]). Let G be an interval graph. For any end vertex v of G, there exists a clique path such that v is a simplicial vertex of the first maximal clique.

Theorem 2.3 (The end vertex theorem
The converse of Theorem 2.3 is also true, and it is implied by the following characterization of interval orderings. Let G be an interval graph with maximal cliques, and let K 1 , K 2 , . . . , K be a clique path of G. We say an ordering σ of V(G) is consistent with the clique path if u < σ v for any pair of vertices u and v with lp(u) < lp(v); in other words, σ can be represented as Proof. The sufficiency is obvious, and hence we focus on necessity. We prove it by induction on n. It is vacuously true for the base case, when G contains a single vertex. Now suppose that the claim is true for all graphs of order n − 1. We may assume without loss of generality that σ(v i ) = i for i = 1, . . . , n. By Proposition 2.1, σ is an LBFS ordering of G, and hence by the perfect elimination theorem (Theorem 2.2), v n is simplicial in G, and v n−1 is simplicial in G − {v n }. By the induction hypothesis, there is a clique path of G − {v n } that is consistent with the ordering v 1 , . . . , v n−1 ; denote by K the last maximal clique of this clique path.
Suppose first that there is a true twin of v n (i.e., another simplicial vertex of G in N[v n ]).

In this case, the simplicial vertex
Thus, adding N[v n ] after K gives the desired clique path for G. Theorem 2.3 has the following corollary, which has been observed by Gimbel [12]. What concerned Gimbel are the end intervals; an end interval is an interval with the smallest left endpoint or the largest right endpoint in an interval representation. Although by the end vertex theorem, every end vertex can be represented by an end interval, the other direction does not hold in general; e.g., neither of vertices 2 and 3 in Figure 4 is an end vertex but tey can have end intervals. Built on Lekkerkerker and Boland [18], Gimbel gave a complete characterization of end intervals, of which Lemma 2.5 is one part. Figure 4). By Theorem 2.3, an LBFS of the bull, disregarding where it starts, ends with a degree-1 vertex. Let us use the bull to motivate our first variation of LBFS. Intuitively, to use LBFS to recognize an interval graph, it makes more sense to start from one end vertex, i.e., 1 or 4 in the bull. However, an LBFS starting from vertex 1 cannot distinguish vertices 3 and 5, while an LBFS starting from vertex 4 can. If we conduct LBFS twice, from 1 and 4 respectively, then they may produce complementary information on the graph, which can be used to get a full picture of the graph. Formally, for an LBFS ordering σ of G and v ∈ V(G), we use N σ (v) to denote the set of neighbors of v that are earlier than v in σ, i.e.,

Lemma 2.5 ([12]). Let G be an interval graph. An end vertex of G cannot be the degree-2 vertex of a bull (vertex 5 in
The v-snapshot in σ, denoted by S σ (v), comprises the vertices that are adjacent to all vertices in N σ (v) and that are visited not earlier than v. Note that S σ (v) is precisely S defined in step 2.1 in the (σ(v))th iteration. There are precisely n snapshots in an LBFS, of which the first is always For an LBFS of the bull starting from vertex 1, the third snapshot is {3, 5}. Not able to distinguish them from this side, we check the other direction-in any LBFS starting from vertex 4, vertex 3 is visited before vertex 5-and thus we probably should visit vertex 5 first.
Instead of running LBFS twice from different ends, Simon [25] proposed a new procedure. Apart from the graph G, the procedure LBFS + (G, σ) takes an LBFS ordering of G as input, and it replaces step 2. We usually use σ + to denote the output of LBFS + (G, σ). Unlike the LBFS itself, which may output different ordering dependent on the vertex selection in step 2.2, an LBFS + ordering is unique for any given LBFS ordering σ. For example, if σ = 1, 2, . . . , 8 for the graph in Figure 2, then σ + has to be 8, 2, 7, 6, 5, 4, 3, 1 . Indeed, for a complete graph, any ordering σ is a valid LBFS ordering, while σ + has to be the full reversal of σ because every snapshot of σ + consists of all the unvisited vertices.
For any graph G and any LBFS ordering σ of G, the first snapshot of σ + is V(G), and thus its first vertex is the last vertex of σ| V(G) = σ, i.e., the end vertex of σ. Corneil et al. [8,6] characterized end vertices of LBFS + orderings of an interval graph. Lemma 2.6 (The flipping lemma [8,6]). Let G be an interval graph. A vertex z is an end vertex if and only if for any LBFS ordering σ of G with σ(z) = 1, the ordering LBFS + (G, σ) ends with z.
A subset M of vertices forms a module of G if for any pair of vertices u, v ∈ M, a vertex x ∈ M is adjacent to u if and only if it is adjacent to v as well; e.g., {3, 4, . . . , 7} of the graph in Figure 2. The set V(G) and all singleton vertex sets are modules, called trivial. A graph on four or more vertices is prime if it contains only trivial modules. The following observation of Hsu [14] is behind Hsu and Ma's recognition algorithms for interval graphs [15].

An appetizer: unit interval graphs
In a unit interval representation, every interval has the same length, and a graph is a unit interval graph if it has a unit interval representation. For example, the bull is a unit interval graph, while the graph in Figure 2 is not. An interval representation is proper if no interval in the representation properly contains another, and proper interval graphs are defined accordingly. A unit interval representation is necessarily proper, but the other way does not hold true in general. A nontrivial observation of Roberts [23] states that these two subclasses of interval graphs actually coincide. This section gives a self-contained presentation of a linear-time algorithm that uses LBFS and LBFS + to recognize proper interval graphs. Every statement toward the main result will be derived from scratch, though not necessarily by formal proofs. (Since we are not proving the equivalence between unit interval graphs and proper interval graphs, strictly speaking, it is not self-contained for recognizing unit interval graphs.) An ordering σ of V(G) is an umbrella ordering if for any triple of vertices u, v, w of G with u < σ v < σ w, vertices u and w are adjacent if and only if they are both adjacent to v. Given a proper interval representation, the left endpoints of all vertices, from the smallest to the largest, with ties broken arbitrarily, induce an ordering of V(G). One can obtain the same ordering by considering all the right endpoints. On the one hand, it is trivial to see that this ordering is an umbrella ordering. On the other hand, from an umbrella ordering σ of a graph G, we can construct a proper interval representation by setting where u is the last vertex in σ| N [v] . We rely on the reader to verify that the resulting representation is indeed proper. Therefore, a graph G is a unit interval graph if and only if it has an umbrella ordering [20]. From (PI) one can also see that a unit interval graph has a proper representation in which all the endpoints are integers between 1 and n 2 . On the other hand, in general, a unit representation with only integral endpoints has to use very large integers, and this suggests the difficulty of building unit representations. The following fact is immediate from the definition of umbrella orderings, and we can also see it through the representation I derived with (PI) from an umbrella ordering: The reversal of σ is precisely the right endpoints of the intervals in I in decreasing order. We have mentioned in Section 2 how to verify a given ordering σ of V(G) is an interval ordering of the graph G. Conducting this test twice, once for σ, and the other for the reversal of σ, would verify whether σ is an umbrella ordering: The answer is "yes" if and only it both σ and σ + pass the test. Indeed, the test on σ verifies uw ∈ E(G) ⇒ uv ∈ E(G), and the other verifies uw ∈ E(G) ⇒ vw ∈ E(G), both for all u < σ v < σ w. 4 In the rest we will be focused on unit interval graphs.
The claw in Figure 5 is an interval graph but not a unit interval graph. We rely on the reader to check that there cannot be a way of arranging a proper interval representation for the four vertices in the claw. The non-existence of claws forces unit interval graphs to have very simple clique paths. Recall that for a vertex v, we use lp(v) and rp(v) to denote the indices of the first and, respectively, last maximal cliques containing v in a clique path. Let G be an unit interval graph, and let K 1 , K 2 , . . . , K be a clique path of G.
, contains a simplicial vertex, then for every v ∈ K p , at least one of lp(v) and rp(v) is p.
Proof. Suppose for contradiction to assertion (i) that lp(v) < p and rp(v) > p. Since both K p−1 and K p+1 are maximal cliques of G, there must be a vertex x ∈ K p−1 \ K p , and a vertex z ∈ K p+1 \ K p . By assumption, there is a simplicial vertex y with lp(y) = rp(y) = p. But then {v, x, y, z} induces a claw, which is impossible.
For assertion (ii), since K p is a maximal clique, there exists x with rp(x) = p. If lp(x) < p, then we are done. Now that lp(x) = p, then x is simplicial. By assertion (i), every vertex in Let K 1 , K 2 , . . . , K be a clique path of a connected unit interval graph G. From Proposition 3.2(i) we can conclude that any simplicial vertex v in K i with 1 < i < is the degree-two vertex of a bull. By Lemma 2.5, v cannot be end vertex, and by the perfect elimination theorem (Theorem 2.2), all the end vertices of G are in K 1 and K . Therefore, by Theorem 2.4, the two ends of any clique path of G must be K 1 and K . The same argument applies to the connected unit interval subgraph induced by −1 i=2 , with clique path K 2 , . . . , K −1 . It is nontrivial but one can show that K , K 2 , K 3 , . . . , K −1 , K 1 is not a clique path of G. We can continue this argument to conclude that a connected unit interval graph has a unique clique path. Yet another way to derive this fact is through Corollary 2.8 and the simple structure of a unit interval graph that has a universal vertex. If a connected unit interval graph G contains a non-clique module M, then N(M) comprises universal vertices, which has no impact on the arrangement of clique paths, and G[M] either is a connected unit interval graph in which every nontrivial module is a set of true twins, or consists of two disjoint cliques with no edges in between. For the sake of completeness, we give a direct and simple proof. Proof. Let G be a connected unit interval graph with maximal cliques, and let K 1 , K 2 , . . . , K be a clique path of G, denoted by K. Suppose to the contradiction of the theorem that there is another clique path K of G that is neither K nor its reversal. We can find a minimal subsequence K p , . . . , K q , 1 p q such that they appear neither in this order or its reversal in K . Let G be the subgraphs induced by q i=p K i , and let K denote the sequence of these cliques as they appear in K . It is easy to use the definition of clique paths to verify that both K p , . . . , K q and K are clique paths of G . By the minimality, one of K p and K q is at the end of K . We may assume without loss of generality that K p is at one end of K , then by the minimality, K has to be K p , K p+1 , . . . , K r−1 , K q , K q−1 , . . . , K r+1 , K r for some r with p < r < q. Since G is connected, there is a vertex v in K r−1 ∩ K q , and by the definition of clique paths, v is also in K r . On the other hand, since K r is the last clique in K , it contains a simplicial vertex of G . We have thus a contradiction to proposition 3.2(i).
It should not be surprising that we can transform proper interval representations, clique paths, and umbrella orderings of a unit interval graph to each other. Since there is no special requirement of clique paths of a unit interval graph, transforming proper interval representation to a clique path is the same as a general interval representation, while transforming an umbrella ordering v 1 , . . . , v n to a clique path can be done as follows. For each vertex v i with the last neighbor v j , the vertex set {v i , . . . , v j } is a clique, and keeping the maximal ones in the original order gives a clique path. On the other hand, the transformations from a clique path to the other two are more subtle. Let G be a connected unit interval graph. We may assume without loss of generality that G is not complete, and let K 1 , K 2 , . . . , K be a clique path of G. To derive a proper interval model, we need to set , where x and y, which are required to ensure that the model is proper, can be calculated in a similar manner as the fractional number in (PI). In an umbrella ordering, a pair of true twins can appear in an arbitrary order. For a pair of vertices u and v that are not true twins, u < σ v if and only if Theorem 3.3 has the following corollary.

Corollary 3.4.
Let G be a connected unit interval graph, and let σ 1 and σ 2 be umbrella orderings of G. Then σ 2 can be obtained from σ 1 or its reversal by re-ordering true twins.
Corollary 3.4 implies the famous characterization of Deng et al. [9], which states that a unit interval graph without true twins has a unique umbrella ordering, up to full reversal. To find an umbrella ordering of G, it suffices to use characterization (UO) to decide the order of each pair of vertices. It is not difficult to see that if an LBFS starts from a simplicial vertex in K 1 , then it visits the maximal cliques of G on the clique path one by one, and hence is able to tell whether lp(u) < lp(v). On the other hand, an LBFS from a simplicial vertex in K is able to tell whether rp(u) < rp(v). Combining them we are able to recognize unit interval graphs. Recall that an end vertex is the last vertex of some LBFS ordering of G, and note that the first assertion of the following theorem is the end vertex theorem (Theorem 2.3), and the proof given here works only for unit interval graphs. Lemma 3.5. Let G be a connected unit interval graph with maximal cliques. Let K 1 , K 2 , . . . , K be a clique path, and σ an LBFS ordering of G.
(i) The last vertex of σ is a simplicial vertex in K 1 or K .
(ii) If σ starts from an end vertex in K 1 , then for i = 1, . . . , − 1, vertices in K i are visited before those in K i+1 \ K i .
(iii) If σ starts from an end vertex in K 1 , then for each proper snapshot Proof. All the assertions hold trivially or vacuously when G is complete. Henceforth we assume that G is not complete, hence > 1. Let v be the first vertex of σ. We first show that for every pair of vertices x and y, if rp(v) < lp(x) < lp(y), then x < σ y. Suppose for contradiction that rp(v) < lp(x) < lp(y) but y < σ x, and let x, y be chosen in way that (A1) lp(x) is the smallest among all such pairs; and (A2) y is the first in σ for the fixed x. By assumption (A2), lp(u) lp(x) for every vertex u ∈ N σ (y)\N(v). Thus, if a vertex in N σ (y) is adjacent to y, then by the definition of clique paths, it has to be adjacent to x as well. By Proposition 3.2(ii), there exists some vertex w with lp(w) < rp(w) = lp(x), then w ∈ N(x) \ N(y). Note that w < σ y: It follows from the procedure LBFS if w is adjacent to v, and by assumption (A1) otherwise. In summary, the label of y is a proper subset of that of x when it is visited, which is impossible. By Proposition 3.1 and a symmetric argument as above, we can conclude that for every pair of vertices x and y, if rp(y) < rp(x) < lp(v), then x < σ y.
(i) We may assume that v is not a universal vertex. Otherwise we may produce another ordering σ from σ by exchanging the first non-universal vertex in σ and v. It is easy to verify that σ is an LBFS ordering of G if and only if σ is. Note that the last vertex of σ is the last vertex of σ. By procedure LBFS, the last vertex z of σ is not adjacent to v. Suppose without loss of generality that lp(z) > rp(v). Then by the argument above, we must have lp(z) = ; in other words, z is a simplicial vertex in K . A symmetric argument concludes that z is a simplicial vertex in K 1 if rp(z) < lp(v).
(ii) For i = 1, it is because all vertices in K 1 are adjacent to the first vertex in σ while vertices in K 2 \ K 1 are not. For i 2, the statement follows from the argument above.
(iii) Suppose that w is the first vertex in σ| S , i.e., S = S σ (w), and we show that p = lp(w) is the required index. By Proposition 3.2(ii), there exists a vertex u with lp(u) < rp(u) = lp(w). By (ii), u < σ w, and S is disjoint from K 1 , . . . , We are now ready to prove the main theorem of this section. The key observation is that any pair of vertices that are not true twins can be distinguished by an LBFS from one end, while an LBFS + ordering combines information from both. For example, vertices 3 and 5 in Figure 4 cannot be distinguished by an LBFS from vertex 1, but can be distinguished by any LBFS from vertex 4. It is the other way for vertices 2 and 5. Theorem 3.6. Let G be a unit interval graph, and let σ be an LBFS ordering of G. If σ starts from an end vertex of G, then LBFS + (G, σ) is an umbrella ordering of G.
Proof. Let σ + = LBFS + (G, σ). We may renumber the vertices such that σ + (v i ) = i. Then by the procedure LBFS + , σ(v 1 ) = n. It suffices to show that p < q for every pair of vertices v p and v q in G satisfying (UO). If lp(u) < lp(v), then p < q follows from Lemma 3.5(ii). Now that lp(u) = lp(v) and rp(u) < rp(v); note that v p and v q are adjacent in G. When σ + visits the first of v p and v q , the other is also in the snapshot. By Lemma 3.5(ii), applied to the reversal of the clique path, v q < σ v p , and thus σ + should choose v p . Therefore, we always have v p < σ + v q , and this concludes the proof. Described in Figure 6 is the algorithm from Corneil [4]. By procedure LBFS + , the first vertex of σ is an end vertex. If G is a unit interval graph, then by Theorem 3.6, σ + is an interval ordering of G. On the other hand, any ordering is incorrect if G is not a unit interval graph.
Input: A connected graph G. Output: Whether G is a unit interval graph.
1. τ ← an LBFS ordering of G; 2. σ ← LBFS + (G, τ); 3. σ + ← LBFS + (G, σ); 4. if σ + is an umbrella ordering of G then return "yes"; 5. else return "no." Figure 6: The three-sweep recognition algorithm for unit interval graphs [4]. Some remarks on Theorem 3.6. Our statement is slightly more general than the one made by Corneil [4]; in particular, we only require σ to start from an end vertex, and it does not need to be an LBFS + ordering. As a result, τ does not need to be an LBFS ordering either. Since the only purpose of the first sweep is to find an end vertex, it can be replaced by BFS. The following lemma from an earlier recognition algorithm of Corneil et al. [5] can help us to find an end vertex with BFS. Indeed, they developed a recognition algorithm for unit interval graphs using only BFS. Note that this statement does not apply to interval graphs.  For the purpose of making an interval ordering, an LBFS from a simplicial vertex in K 1 does not need to distinguish vertices in K p \ K p−1 for p = 1, . . . , . In other words, we only need to consider the first row of (UO). For two vertices u and v with lp(u) = lp(v), we have rp(u) < rp(v) if and only if the degree of u is strictly smaller than v. Therefore, to distinguish such a pair of vertices, we do not really do two sweeps, and it suffices to use the vertex degrees. We are thus motivated to define another variation of LBFS, which always chooses a vertex of the minimum degree from the current proper snapshot. Apart from the graph G, the procedure LBFS δ (G, u) takes an end vertex u of G as input. It replaces step 2.2 of procedure LBFS (Figure 3) by else v ← a vertex with the minimum degree in S; We remark that a variation of LBFS that chooses a largest-degree vertex has been used by Hsu and Ma [15] for finding modules of a chordal graph. We have thus a two-sweep recognition algorithm for unit interval graphs, as described in Figure 7.
Input: A connected graph G. Output: Whether G is a unit interval graph.
1. u ← an end vertex of G; 2. σ ← LBFS δ (G, u); 4. if σ is an umbrella ordering of G then return "yes"; 5. else return "no."  Tarjan and Yannakakis [26] proposed another graph search algorithm for the purpose of recognizing chordal graphs, among others. Also based on adjacencies with visited vertices, an maximum cardinality search (MCS) chooses an unvisited vertex that has the maximum number of visited neighbors. Lemma 3.5(ii) can be re-interpreted as: An LBFS of a unit interval graph from an end vertex visits the maximal cliques one by one. Therefore, it is also an MCS [2], and we have the following corollary, where MCS δ is defined in a similar spirit as LBFS δ .

Interval graphs
Compared to unit interval graphs, an LBFS of an interval graph can jump in an unpredictable and sometimes arbitrary way because of the existence of "long intervals." The graph in Figure 8 was devised by Corneil et al. [8]. Since it is very handy for our explanation, we will use it as the main example for this section, and we henceforth referred to it as G . As indicated by the integral points in the figure, G has 16 maximal clique. Since G is prime, the arrangement of maximal cliques is unique by Theorem 2.7, though the graph admits many different valid interval orderings. After visiting vertices 1 and 2 in G , an LBFS may visit any vertex between 3 and 20 as the third vertex. In general, an LBFS ordering of an interval graph can start from an end vertex, and then quickly jump to another vertex in an arbitrary position in the interval representation, even when the graph is prime. Therefore, one should be extremely careful when talking about the "left" and the "right" for an interval graph G. Listed in Figure 9 are six LBFS orderings of G . In particular, for i = 1, 2, 3, σ + i = LBFS + (G , σ i ). The reader unfamiliar with LBFS + is suggested to go through these orderings before proceeding.  Modules play a very similar role in interval graphs as true twins have played in unit interval graphs. Recall that a set of true twins is a module. Since an interval graph is chordal, if a module M of an interval graph is not a clique, then N(M) has to be a clique: Two nonadjacent vertices from M and two nonadjacent vertices from N(M) would induce a 4-cycle. Let M be a module of a graph G, and let G be the graph G − (M \ {v}) for some vertex v ∈ M. Since we can always use the same intervals for true twins, if M is a set of true twins, then G is an interval graph if and only if G is. In the general case, M is not a clique. We have mentioned that N(M) is a clique; moreover, both G and G[M] are induced subgraphs of G, hence also interval graphs. It is known that these conditions are also sufficient [15]. Given any interval representation I M for G[M] and interval representation I for G , we can always project I M onto the interval for s in I . (Note that we can always modify an interval representation such that every interval has a positive length.) If we take G to be the graph in Figure 2, with M = {3, 4, . . . , 7} and v = 5, then the subgraph G and G[M] are shown in Figure 10(a, b), and Figure 10(c) illustrates the projection of I M onto I(v) in I . Most snapshots in an LBFS ordering are not modules. Since a snapshot S cannot be distinguished by vertices visited before S, we may view S as a "one-sided pseudo-module." A very nontrivial and crucial observation of Corneil et al. [8] is that for a chordal graph, any non-module snapshot S of an LBFS ordering σ has the similar autonomous property; i.e., σ| S is an LBFS ordering of G[S]. Since this is not completely obvious, let us briefly explain why it is true for interval graphs. For this purpose, we are only concerned with those snapshots that are neither cliques nor modules: Any ordering of a clique S is an LBFS ordering of G[S], and we have discussed modules above. We say that a vertex v ∈ S splits a set S, or that v is a splitter of S, if ∅ ⊂ N(v) ∩ S ⊂ S. A set of vertices is a module if and only if it does not have any splitter. Let S be a snapshot of an LBFS ordering σ, and let us fix an interval representation I for G. If S is neither a clique nor a module, then N σ (S) is a clique, and S are precisely intervals intersecting v∈N σ (S) I(v). The splitters of S form one or two cliques, and their intervals intersect the two ends of v∈N σ (S) I(v); e.g., the snapshot S σ 2 (20), which is {6, 7, 9, 10, . . . , 20} of σ 2 , has two splitters, 5 and 21. If an LBFS ordering of G visits a splitter of S before S itself, e.g., σ + 1 , σ + 2 , or σ + 3 , then S is visited from one end to the other. Otherwise, no splitter of S can be visited before the vertices in S have been finished. In either case, the ordering of S is decided by G[S] itself.
Combining these observations on modules and snapshots, we have the following theorem, which consumes all the modules of G and all the snapshots of all possible LBFS orderings of G.

Theorem 4.1 (The interval LBFS theorem [8]). Let G be an interval graph and let σ be an LBFS orderings of G. For any snapshot S and any module M of G[S], the sub-ordering σ| M is an LBFS ordering of G[M].
The execution of LBFS only considers adjacencies in one direction, which are not sufficient to tell whether a snapshot is a module or not. We want to conduct multiple sweeps of LBFS, and use information gleaned from the previous runs to decide whether a snapshot S is a module of G, and more importantly, find a splitter of S to orient G[S], if S is not a module of G.
We use the examples in Figure 9 to motivate the main idea of the algorithm. Suppose that σ is an LBFS ordering of an interval graph G, and that S is a non-module snapshot of G. In general, the splitters of S can sandwich S from both sides, e.g., S σ 2 (20). A nontrivial observation is that if σ is an LBFS + ordering, then all the splitters of S are at the same side of S. In this case, we do not need to worry if S is a clique either. Now let v be a splitter of non-clique non-module snapshot S. Note that v has to be after S in σ; otherwise S cannot be a snapshot. Inspired by the algorithm for unit interval graphs, one may expect that in LBFS + (G, σ), vertex v will be visited before S, thereby telling S apart. As shown by σ 1 and σ + 1 in Figure 9, this natural idea is not true for interval graphs; note that σ 1 is LBFS + (G, σ ) for σ : 22, 4, 3, 2, 5, 6, 7, 8, 9, 18, 17, 12, 14, 13, 11, 15, 16, 10, 19, 20, 21, 1. In particular, the highlighted snapshot {6, 7, 9, 10, . . . , 19} of σ 1 has a unique splitter, vertex 5, which is after this snapshot in both σ 1 and σ + 1 . Let us put the six orderings in Figure 9 under a closer scrutiny. We use S to denote the vertex set {6, 7, 9, 10, . . . , 19}, whose only splitter is vertex 5. In all the six orderings, S is a snapshot, and its only splitter is after S . Note that this is decided by vertices before S in σ i , and cannot be changed by re-arranging vertices in S . What we need to do is to find a way to use vertex 5 to orient S even if it is after S . Since G[S ] is prime, vertices 6 and 19 are its only two end vertices. Since σ i , i = 1, 2, 3, starts from vertex 1 and ends at vertex 22, if σ + i , which starts from vertex 22 and ends at vertex 1, is a correct interval ordering of G , then σ + i should be "from right to left." In particular, σ + i | S needs to start from 19, which in turn requires that σ i | S start from 6. Among the three orderings σ i , only σ 3 satisfies this condition. We may informally say that S is "anchored from the left" in σ 3 . One may also note that the snapshot {11, 13, 14, 15, 16}, of which the only splitter is vertex 10, is also "anchored from the left" in σ 3 . On the other hand, the snapshot {3, 4, . . . , 20} of σ 3 is "anchored from the right" by vertices 21 and 22, which does not make a problem because σ + 3 starts from vertex 22, and {3, 4, . . . , 20} is not a snapshot of σ + 3 . As the reader may easily check, σ + 3 is actually an interval ordering of G . These observations motivated the key concept of Corneil et al. [8] and the main observation of Li and Wu [19]. Let σ be an LBFS ordering of an interval graph G, and let S be a snapshot of σ. We say that a vertex v ∈ S is exposed (from S) in σ if N(v) \ (N σ (S) ∪ S) = ∅; i.e., if some neighbor of v is after S in σ. By the definition of LBFS, if v is adjacent to some splitter of S, then it must be exposed; on the other hand, if S is not a clique, then by the perfect elimination theorem (Theorem 2.2), every neighbor after S in σ is a splitter of S. In the example above, vertex 6 is the only exposed vertex from the snapshot S in σ i , i = 1, 2, 3, and vertex 11 is the only exposed vertex from the snapshot {11, 13, 14, 15, 16} in σ 1 and σ 3 . We say that an LBFS ordering σ of an interval graph is well-anchored if for any snapshot S of σ, the sub-ordering σ| S starts from (A1) an exposed vertex from S if one exists; or (A2) an end vertex of G[S] otherwise.
Note that since V(G) itself is a snapshot and a trivial module, a well-anchored ordering always starts from an end vertex of G. We urge the reader to verify that σ 3 is indeed well-anchored.
As demonstrated above, if a snapshot S of a well-anchored ordering σ is again a snapshot in LBFS + (G, σ), then the first vertex of S can help us to orient S. As we will show below, if σ is well-anchored, then LBFS + (G, σ) must be an interval ordering of G.
However, it is not immediate clear how to produce in linear time an LBFS ordering that is well-anchored. Indeed, it is already very challenging to decide whether an exposed vertex exists in a snapshot, which is equivalent to testing whether a set is a module. This difficulty is manifested by the fact that an LBFS checks adjacencies with visited vertices, while a splitter of S and an exposed vertex from S, if they exist, are both unvisited at the moment choosing the first vertex of S. The crucial observation is that we do not really need to know whether an exposed vertex exists, and it suffices to make sure that the first vertex is exposed if any one is. Let G be an interval graph, and let τ + be an LBFS + ordering of G. We conduct a new LBFS π from the last vertex of τ + . Whenever a proper snapshot S with more than one vertex is met, we proceed as follows. In the first case, some vertex x ∈ N(S) was before S in τ + but after S in π. If S ⊆ N(x), then every vertex in S is exposed. Otherwise, x is a splitter of S, and then by the procedure LBFS, the first vertex of σ| S must be adjacent to the first splitter of S in τ + (not necessarily x). Therefore, the first vertex of σ| S is exposed. In the rest, every vertex x ∈ N(S) that is after S in π is after S in τ + as well. (Note that x is necessarily a splitter of S when S is not a clique, but as said we would not bother ourselves with whether this is true.) It suffices to find a vertex in S that has a neighbor after S in τ + , and in the absences of such a vertex, we take the last vertex of τ + | S . The procedure is summarized in Figure 11. It is worth stressing again that the procedure does not calculate the maximal cliques or the modules explicitly. The reader may verify that LBFS ↑ (G, σ + 1 ) is precisely σ 3 in Figure 9.
Output: A well-anchored ordering of G if G is an interval graph.
v p ← the first vertex of τ + | S ; 2.3.
if there exists < p such that v ∈ N(v p ) and π(v ) is unset then π(v p ) ← i; 2.5.
else if there exist v ∈ S and v r ∈ N(v ) such that r > q then π(v ) ← i; 2.6. else π(v q ) ← i; \ \In this case S is a module of G.

2.7.
for each unvisited neighbor of v do add i to label(v); 3. return π.  Proof. Note that at the beginning of the procedure, we have renumbered the vertices such that τ + (v i ) = i for all i = 1, . . . , n. Let π =LBFS ↑ (G, τ + ). It is clear from the procedure that the ith vertex of π, chosen in step 2.4, 2.5, or 2.6 of the ith iteration is in S, and thus π is an LBFS ordering of G. We need to show that for every i = 1, . . . , n, the ith snapshot of π satisfies the conditions in the definition of well-anchored orderings. Let us fix an i and suppose that π(v s ) = i, and let us use S to denote the ith snapshot, i.e., S π (v s ).
In the first case, the procedure enters step 2.4. There is a vertex v ∈ N(v p ) \ N π (v p ) with < p. The selection of p and the fact < p imply v ∈ S; i.e., v is after S in π. Thus, v p , the first vertex of π| S , is exposed from S in π. Henceforth we may assume that the condition of step 2.4 is not true. Then and hence v q is also in the snapshot S τ + (v p ) by the rule of LBFS. The selection of p and q then implies S ⊆ S τ + (v p ). By the interval LBFS theorem (Theorem 4.1), τ + | S is an LBFS ordering of G[S], of which v q is the last vertex. Thus, v q is an end vertex of G[S]. On the other hand, since In the second case, S is a module. If there exists a vertex in S that is exposed from S, then any vertex in S is exposed from S; thus S satisfies condition (A1). Now that no vertex in S is exposed from S, we need to make sure that S satisfies condition (A2); i.e., v s is an end vertex of G[S]. Again, this is trivial when S is a clique, of which every one is an end vertex. Now suppose that S is not a clique, then a vertex v r ∈ N(S) with r > q would contradict the perfect elimination theorem (Theorem 2.2). Thus, the procedure will skip step 2.5 and enter step 2.6, and then v s = v q .
In the rest, S is not a module of G. Let v r be a splitter of S; since S ⊆ S τ + (v p ), we must have r > p by the rule of LBFS. We show by contradiction that r > q. Suppose that r < q, then v r ∈ S τ + (v p ), and by the definition of snapshots, N τ + (v p ) ⊆ N(v r ). If S is a clique, then from S ⊆ N[v r ] and the fact that v p is simplicial in G[S] it can be inferred that v r and v p are not adjacent. As a result, the (p + 1)st snapshot of τ + , which is S τ + (v p ) ∩ N(v p ), contains v q but not v r , a contradiction to r < q. Now suppose that S is not a clique. Since an LBFS ordering τ + | S of G[S] starts with v p and ends with v q , both simplicial vertices in G[S], we can conclude that v p and v q are not adjacent. Since v r is after S in π, by the rule of LBFS, there exists a vertex v j ∈ N π (S) \ N(v r ). By the definition of snapshots, v j is adjacent to both v p and v q . Since v j is adjacent to a proper and nonempty subset of S τ + (v p ), it is not in N τ + (v p ). By the perfect elimination theorem (Theorem 2.2), we can infer from v p v q ∈ E(G) that (i) v r is not adjacent to both v p and v q because v p < π v q < π v r ; and (ii) j < q because v j is adjacent to both v p and v q . Thus, v j is in and v j is adjacent to v p but not v r , we have v r ∈ N(v p ). Since r < q, there must be some v k ∈ N(v r ) \ N(v q ) with k < j; moreover, v k is in S τ + (v p ) because both v r and v q are both in S τ + (v p ). Thus, p < k < j. As a result, both v j and v k are adjacent to v p , which further implies that v k and v j are adjacent because v p is simplicial , has degree two in this bull, contradicting Lemma 2.5.
We have thus concluded that r > q. Since ∅ ⊂ N(v r ) ∩ S ⊂ S, it follows that v r ∈ N π (S). Therefore, the condition of step 2.5 must be true. (One may note that this means the procedure can reach step 2.6 only when S is a module of G.) Then v s is exposed from S in π because it is adjacent to some splitter of S. This concludes the proof.
We are ready to present the main algorithm for recognizing interval graphs in Figure 11, which is very straightforward now. Note that we use consistent symbols in the procedure LBFS ↑ and the main algorithm. In this rest of this section, we always use τ, τ + , π, and π + to denote the LBFS orderings of G produced by the first four steps of this algorithm.
Input: A connected graph G. Output: Whether G is an interval graph.

Lemma 4.3 ([19]
). Let π be a well-anchored LBFS ordering of an interval graph G, and let S be a non-clique snapshot of π + . If the first vertex of π| S is not exposed from S in π + , then S is a module of G.
Proof. For the proof we may renumber the vertices in a way that π(v i ) = i for all i = 1, . . . , n.
Suppose that v p the first vertex of π| S . Since v p is not exposed from S in π + , we have N(v p ) \ S = N π + (S). By the selection of p, and thus every vertex in N π (v p ) is adjacent to all vertices in S because S is a snapshot of π + . From (2) we can also conclude N π (v p ) ⊆ N(v j ) for every v j ∈ S \ {v p }. The selection of p implies j > p, and thus v j ∈ S π (v p ) by the rule of LBFS. In other words, S ⊆ S π (v p ), and then S π (v p ) is not a clique because S is not a clique,. By the definition of snapshots, every vertex v i ∈ N(v p ) \ S = N π + (S) is adjacent to all vertices in S, and then by the perfect elimination theorem (Theorem 2.2), v i cannot be after S in π. Thus, v p is not exposed from S π (v p ) in π. Since π is a well-anchored ordering, S π (v p ) has to be a module of G, and v p is an end vertex of G[S π (v p )]. By the flipping lemma (Lemma 2.6), then v i is adjacent to all the vertices in S π (v p ), which contradicts the perfect elimination theorem (Theorem 2.2). Therefore, N(S) = N π + (v p ), which means that S is a module of G.
Before the main theorem of this section, we need two more simple properties on modules. The first property extends the similar statement on general LBFS ordering, and is quite natural. Recall that LBFS + is deterministic: LBFS + (G, σ) is unique for any graph G and any LBFS ordering σ of G. . Note that then M is not a clique. By the perfect elimination theorem (Theorem 2.2), there is no vertex in N(M) that is after M in π. Since M is a module, a splitter of S π| M (v) is in M, and thus cannot be in S π (v). Thus, S π (v) is not a module of G, and by the definition of well-anchored orderings, v is exposed from S π (v) in π. Now that v is adjacent to some vertex in M that is after S π| M (v) in π, it is exposed from S π| M (v) in π| M . Thus, π| M is well-anchored.
For the proof of π + | M = LBFS + (G, π| M ), we may renumber the vertices in a way that LBFS + (G, π| M ) = v 1 , v 2 , . . . , v |M| , with vertices in V(G) \ M arbitrarily from v |M|+1 to v n . Suppose for contradiction π + | M = LBFS + (G, π| M ), and let i be the smallest number such that π + | M (v j ) = i, with i = j. Let S = S π + (v j ). By the selection of i and the definition of modules, the set S ∩ M is precisely the vertices in the ith snapshot of LBFS + (G, π| M ). By the rule of LBFS + , the first vertex of π + | S should be the last vertex of π| S , which is v i . We have a contradiction.
We need a constructive version of Theorem 2.7. The following lemma implies Theorem 2.7.

Lemma 4.5.
Let G be an interval graph with maximal cliques. Let K 1 , K 2 , . . ., K and K b(1) , K b(2) , . . ., K b( ) be two different clique paths of G. If there are p and q with 1 p < q < such that b(p) = 1 and b(q) = , then is a nontrivial module of G.
Since v is in a clique that is between K b( ) and K , in at least one of the two clique paths. It follows from the definition of clique paths that If j ∈ J for every maximal clique K j containing v, then and thus N(v) \ U ⊆ K b( ) ∩ K . Now suppose that there exists j ∈ J such that v ∈ K j , then j < b( ) and there is k < q such that b(k) = j. Then since v can be found in both sides of K b( ) in the first clique path, it has to be in K b( ) as well. For the same reason, v ∈ K . But then v is in K b( ) ∩ K , and should not be in U, a contradiction. This concludes the proof.
To prove the main lemma, we show that π + is consistent with some clique path K of G. The main strategy is that if this is not true, then we can use Lemma 4.5 to identify a nontrivial module of G. This cannot happen for a prime graph. In general, however, G might have modules.
If a module that is maximal in a certain sense is a counterexample, we work on this module only. 6 Otherwise, by virtue of Lemma 4.3, we can assume that for each M of these modules, σ| M is consistent with the sub-path of K for M. Again, if σ is not consistent with K, then we use Lemma 4.5 to identify a module of G, and we end with a similar contradiction. Note that for any non-clique module M of G, the set M \ U, while U is the set of universal vertices of G[M], is also a module of G. Lemma 4.6 ([19]). Let π be an LBFS ordering of an interval graph G. If π is well-anchored, then LBFS + (G, π) is an interval ordering of G.
Proof. We may assume that G is connected and has no universal vertices. By Lemma 4.4, if G is not connected, then we may work on its components one by one; if G has a set U of universal vertices, we may consider G − U. We say that a non-clique module has no universal vertex and M is maximal in this sense; i.e., the only module of G that does not have universal vertices and properly contains M is V(G) itself. Since a major module M is not a clique, N(M) is a clique.
We argue that two major modules are disjoint. Suppose for contradiction that the intersection of two major modules We argue that in any clique path of G, (a) maximal cliques containing vertices in a major module M are consecutive, and (b) they can be replaced by any clique path of the subgraph induced by N[M]. Suppose that K 1 , K 2 , . . ., K is a clique path of G, where p and q are the smallest and, respectively, largest indices such that K p , K q ⊆ N[M]. By the selection of p and q, if i < p or i > q, then K i ∩ M = ∅; otherwise K i \ M ⊆ N(M), and then K i ⊆ N[M]. As a result, when p > 1 and when q < respectively. Now that M ⊆ q i=p K i \ (K p ∩ K q ), we have q > p because M is not a clique. We then show that q i=p K i \ (K p ∩ K q ) ⊆ M; i.e., they are equivalent. It suffices to show that q i=p K i \ (K p ∩ K q ) is actually a module of G and no vertex is universal in it. The first follows from that is absent from at least one of K p and K q , and hence cannot be universal. The fact (b) follows from (a), (3), and the definition of clique paths.
Let π + = LBFS + (G, π). For the rest of the proof we renumber the vertices in G in a way that π + (v i ) = i for i = 1, . . . , n. We prove by contradiction that there is a clique path of G that is consistent with π + . We may assume that for each major module M of G, there exists a clique path K M that is consistent with π + | M ; otherwise, by Lemma 4.4, we may focus on G[M] and its orderings π| M and π + | M . We fix a clique path K for G such that for every major module M, the sub-path of K for G[M] is consistent with π + | M ; in particular, the first vertex in π + | M is in the first maximal clique of G[N [M]]. Note that it exists because the two properties on major modules we proved above. Starting from an arbitrary clique path of G, for each major module M, we can replace the sub-path for N[M] by one consistent with π + | M .
Suppose for contradiction that π + is not consistent with K. There exists a pair of vertices v p and v q in G such that p < q but lp(v p ) > lp(v q ). Let them be chosen such that p is the minimum and rp(v q ) is minimum with respect to this fixed p. We denote by r = lp(v q ) and t = lp(v p ), and let S = S π + (v p ) and X = N π + (v p ).
By the selection of p, for all i = 1, . . . , p − 1, we have lp(v i ) lp(v q ). Therefore, X ⊆ N(v q ), and v q is in the snapshot S. We argue that v q is a simplicial vertex of G. Otherwise, by the definition of clique paths, there exists a vertex v j with rp(v j ) = lp(v q ) < rp(v q ), and then j < p by the selection of v p . But since v j ∈ N(v q ) \ N(v p ), LBFS should visit v q before v p . Now that v q is simplicial, from t > r we can conclude that v p and v q are not adjacent. As a consequence, X is a clique. We also argue that S is not a module of G. If S is a module, then there is a major module M such that ( Let K r and K t be the first and, respectively, the last maximal cliques in K that is a subset of S ∪ X. For each vertex v i that is adjacent to all vertices in S, if i p, then v i ∈ S; if i < p, then v i ∈ X. Therefore, no vertex in V(G) \ (S ∪ X) can be adjacent to all vertices in S and X. As a result, every maximal clique K of G[S ∪ X], which contains X as a subset, is a maximal clique of G. Moreover, every maximal clique K of G wih X ⊆ K and K ∩ S = ∅ is a subset of S ∪ X. In particular, K r , K t ⊆ S ∪ X. Thus, r r < t t , and by assumption, every vertex in K 1 , . . ., K r −1 are before v p in π + . Another consequence is that K j \ X ⊆ S for all j with r j t . Therefore, any vertex after S in π + is in a clique K j with j > t . By the definition of clique paths, we can conclude that all the exposed vertices from S in π + belong to K t .
By the interval LBFS theorem (Theorem 4.1), v p is an end vertex of G[S]. Therefore, there exists a clique path K for G[S ∪ X] in which K t is at one end. We may assume without loss of generality that K t is the first of K . On the other hand, let v z be the first vertex of π| S that is not universal in G[S]. We have seen that S is not a module of G, and thus v z is exposed from S in π + by Lemma 4.3. By the interval LBFS theorem (Theorem 4.1), π| S is an LBFS ordering of G[S], and thus the first non-universal vertex v z and the last vertex v p cannot be adjacent. Further, from v z ∈ K t we can conclude that v p ∈ K t and t < t . Thus, in the clique path K r , K r +1 , . . ., K r , K r+1 , . . ., K t , . . ., K t for G[S ∪ X], the clique K t is not an end.
If K r is before K t in K , then by Lemma 4.5, there is a module M of G[S ∪ X] that contains all vertices in t j=r K j \ (K r ∩ K t ). From the definition of clique paths it can be inferred that M is disjoint from K t , and thus M does not contain any exposed vertex of S. On the one hand, no splitter of S is adjacent to M; on the other hand, there is no splitter of M in S. Thus, M is a module of G, contradicting the assumption. Therefore, K r is after K t in K . Again, by Lemma 4.5, there is a module M of G[S ∪ X] that contains all vertices in t j=t K j \ (K t ∩ K t ). Note that both v p and v z are in M, and X ⊆ K t ∩ K t . If G[M] is connected or if X ⊂ K t ∩ K t , then an LBFS ordering of G[S] from v z cannot end at v p : Before vertices in M are exhausted, there is a vertex in M whose label is a proper superset of K t ∩ K t , while the label of any vertex in (S ∪ X) \ M is a subset of K t ∩ K t . Therefore, K t \ K t = K t \ X and K t \ K t = K t \ X, and they belong to different components of G[S]. Moreover, K r \ X is in another component of G[S].
Then the components of G[S] containing K r \ X and K t \ X form a module M of G, and M is disjoint from K t . Thus, M is a module of G. But this contradicts our assumption. The proof is now complete.
It is not difficult to prove the following result. Since we are not using it, we omit the proof. Remark 4.7. Let σ be an LBFS + ordering of an interval graph G, and let M be a major module of G. If M does not contain the first vertex of σ, then vertices in M appear consecutive in σ.
As a final remark, Theorem 3.6 also implies Theorem 4.30 of [19], namely, the algorithm for interval recognition always returns a correct umbrella ordering for a unit interval graph.

Implementation and concluding remarks
All the procedures are implemented using the idea of partition refinement [13]. We sketch here the steps very briefly. Similar as LBFS + , we can start LBFS δ with the vertices ordered by their degrees. The procedure LBFS ↑ is more complicated. Recall that at the beginning we renumber the vertices according to τ + . We maintain an array d that is initialized as d[i] = |{v j ∈ N(v i ) | j < i}|; i.e., d[i] is the number of neighbors of v i that are before v i in τ + . We start the partition procedure with the vertices sorted by max{j | v j ∈ N[v i ]}, and for vertices with the same value, sort them in the reversal of their indices. When a vertex v i is visited, we decrease d[j] for each unvisited neighbor v j ∈ N(v i ). Then condition of step 2.5 of LBFS ↑ is satisfied if and only if d(p) > 0, and for both steps 2.6 and 2.7, it suffices to take the last vertex in the list for the current snapshot.
Among the known recognition algorithms for interval graphs, the ones by Hsu and Ma [15] and Li and Wu [19] are arguably the simplest. However, they are significantly more complicated than the algorithms of Rose et al. [24] for chordal graphs, not to mention the simpler one in Tarjan and Yannakakis [26]. Since interval graphs are conceptually simpler than chordal graphs, it may not be safe to call either of them the ultimate algorithm for the recognition of interval graphs. On the other hand, we believe that they are close to the ultimate algorithm, if such an algorithm does exist. Toward this direction, one step might be better understanding the well-anchored orderings of an interval graph. In particular, can we produce one with only one or two sweeps of graph searches?