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:
“Being a Georgia author is a rather specious dignity, on the same order as, for the pig, being a Talmadge ham.”
—Flannery O’Connor (1925–1964)
“By intervening in the Vietnamese struggle the United States was attempting to fit its global strategies into a world of hillocks and hamlets, to reduce its majestic concerns for the containment of communism and the security of the Free World to a dimension where governments rose and fell as a result of arguments between two colonels’ wives.”
—Frances Fitzgerald (b. 1940)