Schnyder's Theorem - Other Graphs

Other Graphs

As Schnyder observes, the incidence poset of a graph G has order dimension two if and only if the graph is a path or a subgraph of a path. For, the only possible realizer for the incidence poset consists of two total orders that (when restricted to the graph's vertices) are the reverse of each other; otherwise, the intersection of the two orders would include an order relation between two vertices, which is not allowed for incidence posets. But two total orders on the vertices that are the reverse of each other can realize any subgraph of a path, by including the edges of the path in the ordering immediately following the later of the two edge endpoints.

If a graph can be colored with four colors, then its incidence poset has order dimension at most four (Schnyder 1989).

The incidence poset of a complete graph on n vertices has order dimension (Spencer 1971).

Read more about this topic:  Schnyder's Theorem