Interval Graphs, Chronological Orderings, and Related Matters.
Abstract
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1980
- Accession Number
- ADA086224
Entities
People
- Dale J. Skrien
Organizations
- University of Washington