Planarity and Dimension for Graphs and Posets

Abstract

There is a rich history of research relating planarity for graphs and diagrams with the dimension of posets, starting with the elegant characterization of planarity for posets with a zero and a one: they are planar if and only if they have dimension at most 2. Planar posets with a zero (or a one) have dimension at most 3, but Kelly showed that there are planar posets of arbitrarily large dimension. Subsequently, Schnyder proved that a graph is planar if and only if the dimension of its incidence poset is at most 3. Quite recently, Felsner, Wiechert and Trotter have shown that the dimension of a poset with a planar comparability graph is at most 4, while Streib and Trotter have shown that the dimension of a poset with a planar cover graph is bounded as a function of its height.