Hell, Pavol; Huang, Jing Certifying LexBFS recognition algorithms for proper interval graphs and proper interval bigraphs. (English) Zbl 1069.05056 SIAM J. Discrete Math. 18, No. 3, 554-570 (2005). Summary: Recently, D. Corneil found a simple 3-sweep lexicographic breadth first search (LexBFS) algorithm for the recognition of proper interval graphs. We point out how to modify Corneil’s algorithm to make it a certifying algorithm, and then describe a similar certifying 3-sweep LexBFS algorithm for the recognition of proper interval bigraphs. It follows from an earlier paper that the class of proper interval bigraphs is equal to the better known class of bipartite permutation graphs, and so we have a certifying algorithm for that class as well. All our algorithms run in time \(O(m+n)\), including the certification phase. The certificates of representability (the intervals) can be authenticated in time \(O(m+n)\). The certificates of nonrepresentability (the forbidden subgraphs) can be authenticated in time \(O(n)\). Cited in 29 Documents MSC: 05C62 Graph representations (geometric and intersection representations, etc.) 05C85 Graph algorithms (graph-theoretic aspects) 68R10 Graph theory (including graph drawing) in computer science Keywords:bipartite permutation graphs; bipartite trapezoid graphs; proper circular arc graphs; lexicographic breadth first search; certifying algorithms; forbidden subgraph characterizations PDFBibTeX XMLCite \textit{P. Hell} and \textit{J. Huang}, SIAM J. Discrete Math. 18, No. 3, 554--570 (2005; Zbl 1069.05056) Full Text: DOI