Crossing Numbers of Complete Graphs
Noam D. Elkies · Princeton University Press eBooks · 2017
This chapter examines crossing numbers. When a particular graph is drawn on a given surface, what is the smallest possible number of crossings among the edges? The chapter is organized as follows. Section 1 introduces crossing numbers; reviews the surfaces D, R 2, S, M, P, and T and some connections between them; and gives some basic properties of the crossing numbers, culminating with the existence of P Σ for any surface Σ. Sections 2–4 treat crossing numbers on the sphere, projective plane, and torus in turn. Section 5 lists some open problems suggested by this analysis, on the same three surfaces and also on the Klein bottle and beyond. We relegate to an appendix the computation of the integrals that figure in the bounds on P P and P T.