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:
“There is no permanent class of hired laborers amongst us. Twenty five years ago, I was a hired laborer. The hired laborer of yesterday, labors on his own account today; and will hire others to labor for him tomorrow. Advancement—improvement in condition—is the order of things in a society of equals.”
—Abraham Lincoln (1809–1865)
“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)