Editing Interval graph (section)

== Efficient recognition algorithm ==

Determining whether a given graph <math>G=(V,E)</math> is an interval graph can be done in <math>O(|V|+|E|)</math> time by seeking an ordering of the maximal cliques of <math>G</math> that is consecutive with respect to vertex inclusion. Many of the known algorithms for this problem work in this way, although it is also possible to recognize interval graphs in linear time without using their cliques.{{sfnp|Hsu|1992}}

The original linear time recognition algorithm of {{harvtxt|Booth|Lueker|1976}} is based on their complex [[PQ tree]] data structure, but {{harvtxt|Habib|McConnell|Paul|Viennot|2000}} showed how to solve the problem more simply using [[lexicographic breadth-first search]], based on the fact that a graph is an interval graph if and only if it is [[Chordal graph|chordal]] and its [[complement (graph theory)|complement]] is a [[comparability graph]].<ref>{{harvtxt|Fishburn|1985}}; {{harvtxt|Golumbic|1980}}</ref>
A similar approach using a 6-sweep LexBFS algorithm is described in {{harvtxt|Corneil|Olariu|Stewart|2009}}.