Skip to main content
Contribution to Book
Probe Interval Orders
The Mathematics of Preference,Choice and Order: Essays in Honor of Peter C. Fishburn
  • David E. Brown, Utah State University
  • L. J. Langley
Document Type
Contribution to Book
Editor
S.J. Brams et al.
Publisher
Springer-Verlag Heidelberg Berlin
Publication Date
1-1-2009
Disciplines
Abstract

A probe interval graph is a graph with vertex partition PN and to each vertex v there corresponds an interval Iv such that vertices are adjacent if and only if their corresponding intervals intersect and at least one of the vertices belongs to P. If a graph has a transitive orientation on its complement, it is a cocomparability graph, and we can think of it as the incomparability graph of the order given by a transitive orientation of its complement. When the vertices of N have a proper representation (no interval contains another properly), a natural transitive orientation of the complement occurs. We call the order that arises a probe interval order. We characterize which probe interval graphs yield a probe interval order by restrictions placed on {Iv : v ∈ N}, and by the nature of the partition restricted to 4-cycles in the graph. We discuss methods for recognizing cocomparability probe interval graphs, both in the partitioned and non-partitioned case.

Citation Information
Brown, D. E., L. J. Langley, "Probe Interval Orders", S.J. Brams et al. (eds.)The Mathematics of Preference, Choice and Order: Essays in Honor of Peter C. Fishburn, Springer-Verlag Heidelberg Berlin 2009.