Graph Embeddings on Surfaces: A Classical Review of Topological Graph Theory

Abstract

Topological graph theory studies graphs in relation to the surfaces on which they can be drawn. This review presents the main classical ideas of the field in a clear and connected framework. It begins with graph embeddings, Euler’s formula, and the basic principles of planar graphs. It then discusses important classical results, including the theorems of Kuratowski, Whitney, Mac Lane, and Wagner, and explains their role in understanding planarity and graph structure. The review also introduces graph embeddings on more general surfaces and examines key concepts such as genus, rotation systems, dual graphs, and surface colouring. Further topics include maximum genus, genus distributions, excluded minors, and algorithms for deciding whether a graph can be embedded on a fixed surface. Particular attention is given to the relationships among these concepts. Euler-type arguments provide useful numerical restrictions, while subdivisions and graph minors give structural characterisations of embeddability. Rotation systems offer a combinatorial way to describe embeddings, whereas genus-related parameters measure different aspects of their topological complexity. Overall, the review provides an accessible account of the classical foundations of topological graph theory and shows how its major results form a unified framework for studying graphs on surfaces. The historical development of the Heawood map-colouring programme and its relation to complete-graph embeddings is treated explicitly, including the Klein bottle exception and the sphere as the Four Colour Theorem case. Recent work is used to show how classical Kuratowski-type and bounded-genus questions remain active. The final synthesis separates established results from continuing directions in obstruction enumeration, representativity, embedding distributions, and near-planar graph drawing.