3 - Polytopal Graphs

Summary

The {graph} of a polytope is formed by the vertices and edges of the polytope.We often see this graph as an abstract graph and apply methodology from graph theory. A {polytopal graph} is simply a graph of a polytope. Appendix C reviews the relevant graph-theoretical prerequisites. Graphs of 3-polytopes are planar, and thus we review the topological background to study graphs embedded in a topological space. We then study properties of polytopal graphs. We analyse acyclic orientations of graphs of polytopes in Section 3.5; these orientations are related to the shelling orders of the corresponding dual polytopes. We also examine convex realisations of 3-connected planar graphs and Steinitz’s characterisation of graphs of 3-polytopes. The graph of a 3-polytope contains a subdivision of the graph of the 3-simplex, namely $K^{4}$.Section 3.9 shows that this extends to every dimension. Since $K^{5}$ is the 1-skeleton of a $4$-simplex, the nonplanarity of $K^{5}$ is a special case of a theoremof Flores (1934) and Van Kampen (1932) that states the $d$-skeleton of the $(2d+2)$-simplex cannot be embedded in $\R^{2d}$ (Section 3.10).