Partial Orders
Graham Brightwell · 1997
Abstract We explore several connections between graphs and partially ordered sets. We define various graphs and digraphs associated with a partially ordered set, and explore how the properties of the partial order are reflected in these graphs. We consider the incidence order of a graph, and prove Schnyder’s Theorem, that a graph is planar if and only if its incidence order has dimension at most 3. It is possible, and only moderately perverse, to think of a graph as a special kind of partially ordered set. Then again, a partially ordered set can be regarded as nothing more than a special kind of directed graph. One should be wary of concluding that the concerns of one subject are similar to those of the other, or that results from one area are necessarily of use in the other, but it is not unreasonable to expect that there will be connections. This chapter is devoted to some of those links that have proved interesting.