Order Dimension Two
The partial orders with order dimension two may be characterized as the partial orders whose comparability graph is the complement of the comparability graph of a different partial order (Baker, Fishburn & Roberts 1971). That is, P is a partial order with order dimension two if and only if there exists a partial order Q on the same set of elements, such that every pair x, y of distinct elements is comparable in exactly one of these two partial orders. If P is realized by two linear extensions, then partial order Q complementary to P may be realized by reversing one of the two linear extensions. Therefore, the comparability graphs of the partial orders of dimension two are exactly the permutation graphs, graphs that are both themselves comparability graphs and complementary to comparability graphs.
The partial orders of order dimension two include the series-parallel partial orders (Valdes, Tarjan & Lawler 1982).
Read more about this topic: Order Dimension
Famous quotes containing the words order and/or dimension:
“War begets quiet, quiet idleness, idleness disorder, disorder ruin; likewise ruin order, order virtue, virtue glory, and good fortune.”
—Sir Walter Raleigh (1552–1618)
“Le Corbusier was the sort of relentlessly rational intellectual that only France loves wholeheartedly, the logician who flies higher and higher in ever-decreasing circles until, with one last, utterly inevitable induction, he disappears up his own fundamental aperture and emerges in the fourth dimension as a needle-thin umber bird.”
—Tom Wolfe (b. 1931)