Posets and planar graphs

Usually dimension should be an integer valued parameter. We introduce a refined version of dimension for graphs, which can assume a value [ t  − 1 ↕ t ], thought to be between t  − 1 and t . We have the following two results: (a) a graph is outerplanar if and only if its dimension is at most [2↕3]. This characterization of outerplanar graphs is closely related to the celebrated result of W. Schnyder [16] who proved that a graph is planar if and only if its dimension is at most 3. (b) The largest n for which the dimension of the complete graph K n is at most [ t  − 1 ↕ t ] is the number of antichains in the lattice of all subsets of a set of size t  − 2. Accordingly, the refined dimension problem for complete graphs is equivalent to the classical combinatorial problem known as Dedekind's problem. This result extends work of Hoşten and Morris [14]. The main results are enriched by background material, which links to a line of research in extremal graph theory, which was stimulated by a problem posed by G. Agnarsson: Find the maximum number of edges in a graph on n nodes with dimension at most t . © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 273–284, 2005