×

Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs. (English) Zbl 0835.05064

Comparability graphs are undirected graphs whose edges can be directed such that the resulting graph is transitive. Proper interval graphs are intersection graphs of inclusion-free sets of intervals. Proper circular arc graphs are intersection graphs of inclusion-free sets of arcs of a circle. In this paper, an elegant new technique is shown for the recognition of comparability graphs, proper interval graphs, and proper circular arc graphs, and for building the corresponding representations. This technique leads to algorithms that are, for sparse graphs, as efficient as existing algorithms, but that are conceptually simpler.
The authors show that the recognition and representation problems for proper interval graphs and proper circular arc graphs can be stated in terms of finding certain orientations of the edges, namely as a local transitive tournament, or as an acyclic local tournament. These orientations (and a transitive orientation) can be found, if existing, with a technique of the following form: First an auxiliary graph is formed. This auxiliary graph necessarily is bipartite, if the graph is in the class to be recognized. Then, a specific two-coloring of the auxiliary graph is formed; of each component, the lexicographic smallest element is colored with color 1. This lexicographic two-coloring can be transformed to the desired orientation, or, in case of proper interval graphs, it can be seen that the graph is not in the class. In each case, this leads to an algorithm that uses \(O(n + dm)\) time on a graph with \(m\) edges and maximum vertex degree \(d\).

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C20 Directed graphs (digraphs), tournaments
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bang-Jensen, J. Graph Theory 14 pp 371– (1990)
[2] Bang-Jensen, Discrete Math. 128 pp 395– (1994)
[3] , and , Local tournaments and proper circular arc graphs, CSS/LCCR TR90-11, Simon Fraser University, Revised August 1990. · Zbl 0819.68088
[4] Booth, J. Comput. Syst. Sci. 13 pp 355– (1976) · Zbl 0367.68034
[5] , and , Linear time representation algorithms for proper circular arc graphs and proper interval graphs, SIAM J. Comput., in press. · Zbl 0858.05094
[6] , and , Recognition and representation of proper circular arc graphs, in: Integer Programming and Combinatorial Optimization, Proceedings of the Second IPCO Conference (eds. E. Balas, G. Cornuejols, and R. Kannan) (1962), 114–121.
[7] Gallai, Acta Math. Acad. Sci. Hungar 18 pp 25– (1967)
[8] Ghouilà-Houri, C. R. Acad. Sci. Paris 254 pp 1370– (1962)
[9] Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York (1980). · Zbl 0541.05054
[10] , and , Local tournaments and proper circular arc graphs, Algorithms, Lecture Notes in Computer Science (, , and , eds.) Vol. 450 Springer-Verlag, New York (1990) pp. 101–109. · Zbl 0819.68088
[11] and , Linear algorithm for maximum clique and minimum coloring on proper circular arc graphs, SIAM J. Disc. Math., in press.
[12] Huang, J. Combin. Th. (B) 63 pp 200– (1995)
[13] Tournament-like orineted graphs, Ph.D. thesis, Simon Fraser University, 1992.
[14] Klee, Amer. Math. Monthly 76 pp 810– (1969)
[15] Pnueli, Canad. J. Math. 23 pp 160– (1971) · Zbl 0204.24604
[16] Indifference graphs, in: Proof Techniques in Graph Theory (ed. Academic Press, New York, (1969), 139–146.
[17] and , Algorithmic aspects of vertex elimination, Proc. 7-th Annual ACM Symposium on the Theory of Computing (1975) 245–254.
[18] Skrien, J. Graph Theory 6 pp 309– (1980)
[19] Spinard, SIAM J. Comput. 14 pp 658– (1985)
[20] Tucker, Discrete Math. 7 pp 167– (1974)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.