|. If and ?. G. |l, |, then Eq. (66) gives L ? ?1 G,? (?(? )) \ ?[i ? 1] = ?. If |T | = |L ? ?1 G,? (?(? ))|, as we surely have, Eq. (66) leads to L ? ?1 G,? (?(? )) \ ?[i ? 1] = ?, as was to be shown

@. Compute-the and T. , u) ? ?[i ? 1] ? ?[? ? 1] and its size |T |. Determine which is true, this step can be done in O(deg G (?(i))) time

@. If, |. |l, and ?. G. , ? (?(? ))|, according to the Claim and our algorithm description, we should set ?(i) to be ?(? )

@. If, L. , and ?. G. , \ ?[i ? 1] = ?, according to the Claim and our algorithm description, we should proceed to check whether or not it holds f ? (w) > ? and this costs O(1) time. If f ? (w) > ? , we set ?(i) = w and else we set ?(i) = ?(? )

]. P. Baldy and M. Morvan, A linear time and space algorithm to recognize interval orders, Discrete Applied Mathematics, vol.46, issue.2, pp.173-178, 1993.
DOI : 10.1016/0166-218X(93)90027-L

K. S. Booth and G. S. Lueker, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, Journal of Computer and System Sciences, vol.13, issue.3, pp.335-379, 1976.
DOI : 10.1016/S0022-0000(76)80045-1

T. H. Corman, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2001.

D. G. Corneil, A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs, Discrete Applied Mathematics, vol.138, issue.3, pp.371-379, 2004.
DOI : 10.1016/j.dam.2003.07.001

D. G. Corneil, Lexicographic Breadth First Search ??? A Survey, Lecture Notes in Computer Science, vol.3353, pp.1-19, 2005.
DOI : 10.1007/978-3-540-30559-0_1

D. G. Corneil, H. Kim, S. Natarajan, S. Olariu, and A. P. Sprague, Simple linear time recognition of unit interval graphs, Information Processing Letters, vol.55, issue.2, pp.55-99, 1995.
DOI : 10.1016/0020-0190(95)00046-F

D. G. Corneil, E. K. Ohler, and J. Lanlignel, On end-vertices of Lexicographic Breadth First Searches, Discrete Applied Mathematics, vol.158, issue.5, pp.434-443, 2010.
DOI : 10.1016/j.dam.2009.10.001

D. G. Corneil and R. M. Krueger, A Unified View of Graph Searching, SIAM Journal on Discrete Mathematics, vol.22, issue.4, pp.1259-1276, 2008.
DOI : 10.1137/050623498

D. G. Corneil, S. Olariu, and L. Stewart, Asteroidal Triple-Free Graphs, SIAM Journal on Discrete Mathematics, vol.10, issue.3, pp.399-430, 1997.
DOI : 10.1137/S0895480193250125
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.46.8984

D. G. Corneil, S. Olariu, and L. Stewart, The ultimate interval graph recognition algorithm? (extended abstract, Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp.175-180, 1998.

D. G. Corneil, S. Olariu, and L. Stewart, Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs, SIAM Journal on Computing, vol.28, issue.4, pp.1284-1297, 1999.
DOI : 10.1137/S0097539795282377

D. G. Corneil, S. Olariu, and L. Stewart, The LBFS Structure and Recognition of Interval Graphs, SIAM Journal on Discrete Mathematics, vol.23, issue.4, pp.1905-1953, 2009.
DOI : 10.1137/S0895480100373455

C. Crespelle, Fully Dynamic Representations of Interval Graphs, Lecture Notes in Computer Science, vol.5911, pp.77-87, 2010.
DOI : 10.1007/978-3-642-11409-0_7
URL : https://hal.archives-ouvertes.fr/hal-00644222

X. Deng, P. Hell, and J. Huang, Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs, SIAM Journal on Computing, vol.25, issue.2, pp.390-403, 1996.
DOI : 10.1137/S0097539792269095

F. F. Dragan, F. Nicolai, A. Brandst¨adtbrandst¨, and . Brandst¨adt, LexBFS-orderings and powers of graphs, Lecture Notes in Computer Science, pp.1197-166, 1997.
DOI : 10.1007/3-540-62559-3_15

C. M. De-figueiredo, J. Meidanis, C. P. De, and . Mello, A linear-time algorithm for proper interval graph recognition, Information Processing Letters, vol.56, issue.3, pp.56-179, 1995.
DOI : 10.1016/0020-0190(95)00133-W

P. C. Fishburn, Interval graphs and interval orders, Discrete Mathematics, vol.55, issue.2, 1985.
DOI : 10.1016/0012-365X(85)90042-1

J. Gimbel, End vertices in interval graphs, Discrete Applied Mathematics, vol.21, issue.3, pp.257-259, 1988.
DOI : 10.1016/0166-218X(88)90071-6

M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Annals of Discrete Mathematics, vol.57, 2004.

M. Habib, R. M. Mcconnell, C. Paul, and L. Viennot, Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing, Theoretical Computer Science, vol.234, issue.1-2, pp.59-84, 2000.
DOI : 10.1016/S0304-3975(97)00241-7

P. Hell and J. Huang, Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs, Journal of Graph Theory, vol.7, issue.3, pp.361-374, 1995.
DOI : 10.1002/jgt.3190200312

P. Hell and J. Huang, Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs, SIAM Journal on Discrete Mathematics, vol.18, issue.3, pp.554-570, 2005.
DOI : 10.1137/S0895480103430259

P. Hell, R. Shamir, and R. Sharan, A fully dynamic algorithm for recognizing and representing proper interval graphs, SIAM Journal on Computing, pp.31-289, 2001.

W. Hsu, A simple test for interval graphs, Lecture Notes in Computer Science, vol.657, pp.11-16, 1993.
DOI : 10.1007/3-540-56402-0_31

W. Hsu, $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs, SIAM Journal on Computing, vol.24, issue.3, pp.411-439, 1995.
DOI : 10.1137/S0097539793260726

W. Hsu, On-line recognition of interval graphs in O(m + n log n) time, Lecture Notes in Computer Science, pp.1120-1147, 1996.

W. Hsu and T. Ma, Fast and Simple Algorithms for Recognizing Chordal Comparability Graphs and Interval Graphs, SIAM Journal on Computing, vol.28, issue.3, pp.1004-1020, 1999.
DOI : 10.1137/S0097539792224814

L. Ibarra, A Fully Dynamic Graph Algorithm for Recognizing Interval Graphs, Algorithmica, vol.13, issue.3, pp.58-637, 2010.
DOI : 10.1007/s00453-009-9291-6

L. Ibarra, A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs, Lecture Notes in Computer Science, vol.13, issue.3, pp.190-201, 2009.
DOI : 10.1137/0213035

B. Jamison and S. Olariu, On the semi-perfect elimination, Advances in Applied Mathematics, vol.9, issue.3, pp.364-376, 1988.
DOI : 10.1016/0196-8858(88)90019-X

]. N. Korte and R. H. Ohring, An Incremental Linear-Time Algorithm for Recognizing Interval Graphs, SIAM Journal on Computing, vol.18, issue.1, pp.68-81, 1989.
DOI : 10.1137/0218005

D. Kratsch, R. M. Mcconnell, K. Mehlhorn, and J. P. Spinrad, Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs, SIAM Journal on Computing, vol.36, issue.2, pp.326-353, 2006.
DOI : 10.1137/S0097539703437855

C. G. Lekkerkerker and J. C. Boland, Representation of a finite graph by a set of intervals on the real line, Fundamenta Mathematicae, vol.51, pp.45-64, 1962.

P. Li and Y. Wu, Maximal Neighborhood Search and Rigid Interval Graphs, Journal of Graph Algorithms and Applications, vol.17, issue.3, pp.245-264, 2013.
DOI : 10.7155/jgaa.00293

P. Li and Y. Wu, A 4-sweep LBFS certifying algorithm for recognizing interval graphs

P. J. Looges and S. Olariu, Optimal greedy algorithms for indifference graphs, Proceedings IEEE Southeastcon '92, pp.15-25, 1993.
DOI : 10.1109/SECON.1992.202324

W. Lu and W. Hsu, A Clustering Algorithm for Interval Graph Test on Noisy Data, Lecture Notes in Computer Science, pp.2647-195, 2003.
DOI : 10.1007/3-540-44867-5_16

D. Meister, Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs, Discrete Applied Mathematics, vol.146, issue.3, pp.193-218, 2005.
DOI : 10.1016/j.dam.2004.10.001

R. H. Ohring, Algorithmic aspects of comparability graphs and interval graphs, Graphs and Orders, pp.41-101, 1985.

B. S. Panda and S. K. Das, A linear time recognition algorithm for proper interval graphs, Information Processing Letters, vol.87, issue.3, pp.153-161, 2003.
DOI : 10.1016/S0020-0190(03)00298-9

G. Ramalingam and C. P. Rangan, A unified approach to domination problems on interval graphs, Information Processing Letters, vol.27, issue.5, pp.271-274, 1988.
DOI : 10.1016/0020-0190(88)90091-9

A. Raychaudhuri, On powers of interval and unit interval graphs, Congressus Numerantium, pp.235-242, 1987.

D. J. Rose, R. E. Tarjan, and G. S. Lueker, Algorithmic Aspects of Vertex Elimination on Graphs, SIAM Journal on Computing, vol.5, issue.2, pp.266-283, 1976.
DOI : 10.1137/0205021

K. Simon, A new simple linear algorithm to recognize interval graphs, Lecture Notes in Computer Science, vol.553, pp.289-308, 1992.
DOI : 10.1007/3-540-54891-2_22

J. P. Spinrad, Efficient Graph Representations, Fields Institute Monographs, 2003.
DOI : 10.1090/fim/019

W. T. Trotter, New perspectives on interval orders and interval graphs, Lecture Note Series 241, pp.237-286, 1997.