LEXICOGRAPHIC ORIENTATION AND REPRESENTATION ALGORITHMS FOR COMPARABILITY GRAPHS, PROPER CIRCULAR ARE GRAPHS, AND PROPER INTERVAL GRAPHS

摘要

We introduce a simple new technique which allows us to solve several problems that can be formulated as seeking a suitable orientation of a given undirected graph. In particular, we use this technique to recognize and transitively orient comparability graphs, to recognize and represent proper circular arc graphs, and to recognize and represent proper interval graphs. As a consequence, we derive simple new proofs of a theorem of Ghouila-Houri and a theorem of Skrien. Our algorithms are conceptually simpler than (and often of comparable efficiency to) the existing algorithms for these problems. (C) 1995 John Wiley & Sons, Inc. [References: 20]