×

Linear-time representation algorithms for proper circular-arc graphs and proper interval graphs. (English) Zbl 0858.05094

A circular-arc graph is a graph \(G=(V,E)\) that can be represented by circlar arcs (intervals) on a circle in such a way that there is an arc \(I_x\) corresponding to each vertex \(x\in V\) and two vertices \(x\) and \(y\) of \(G\) are adjacent just if \(I_x\) and \(I_y\) overlap. If we can choose the arcs so that no arc is properly contained in any other, then we call \(G\) a proper circular-arc graph. The definition of an interval graph and proper interval graph are analogous where we just replace the word “circle” above by “line”. The main result of this paper is a linear time algorithm to recognize and represent proper circular-arc graphs. The algorithm explicitly uses the fact that (among connected graphs) proper circular-arc graphs are precisely those graphs orientable as local tournaments (whenever two vertices \(x\), \(y\) have an arc to (from) the same vertex \(z\) they must be adjacent). The algorithm uses as a subroutine a new linear time algorithm for representing proper interval graphs. This latter algorithm also depends on an orientation characterization of proper interval graphs.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C75 Structural characterization of families of graphs
05C20 Directed graphs (digraphs), tournaments
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI