This paper is concerned with special interval representations of interval graphs. The basic notion is that of a chronological ordering of an interval graph, which is an equivalence class of interval representations of the graph in question. Consider a reference set P = (l sub 1 ..., (l sub n, r sub 1, ..., r) whose points are to be associated with the respective left and right endpoints of interval representations of a graph having n nodes. Among the questions that are considered in this paper, and are answered both mathematically and algorithmically, are the following: Given an interval graph G with n nodes, which linear orderings on P sub n arise from interval representations of G. Given a partial ordering of P sub n, when can it be expanded to a linear ordering associated with an interval representation of G. How many chronological ordering does a given interval graph have. The theorems and algorithms are applicable to a variety of seriation problems. (Author)
展开▼
