Incidence poset

Incidence posets have been particularly studied with respect to their order dimension, and its relation to the properties of the underlying graph.

The incidence poset of a connected graph G has order dimension at most two if and only if G is a path graph, and has order dimension at most three if and only if G is at most planar (Schnyder's theorem).

[1] However, graphs whose incidence posets have order dimension 4 may be dense[2] and may have unbounded chromatic number.

[3] Every complete graph on n vertices, and by extension every graph on n vertices, has an incidence poset with order dimension O(log log n).

[4] If an incidence poset has high dimension then it must contain copies of the incidence posets of all small trees either as sub-orders or as the duals of sub-orders.