Interval Orders and Interval Graphs: A Study of Partially Ordered Sets

This book explores the intimate connection between finite interval graphs and interval orders. Special attention is given to the family of interval orders that agree with, or provide representations of, an interval graph. Two characterizations (one by P. Hanlon) of interval graphs with essentially unique agreeing interval orders are noted, and relationships between interval graphs and interval orders that concern the number of lengths required for interval representations and bounds on lengths of representing intervals are discussed. Two invariants of the family of interval orders that agree with an interval graph are established, namely magnitude, which affects end-point placements, and the property of having the lengths of all representing intervals between specified bounds. Extremization problems for interval graphs and interval orders are also considered.