What does it mean to draw a graph on a surface

general-topologygraph theory

I am self-studying graph theory, mainly from Bela Bellobas' excellent book 'Modern Graph Theory', but also from various online lecture notes. My difficulty is that I do not understand what is mean to 'draw a graph on a surface'. For instance, in Bellobas' book it refers to the theorem of Heawood from 1890, that

The chromatic number of a graph G drawn on a closed surface of Euler characteristic $\chi \leq 1$ is at most $h(\chi ) = \lfloor{ (7+\sqrt{49-24\chi }/2)}\rfloor$

But, when we talk of 'drawing a graph on a surface', what does it mean about the distribution of points? I can imagine drawing a graph on a torus, and if I draw it sufficiently small compared with the curvature of the torus, then surely properties like planarity will be unchanged, because the graph is effectively on a planar surface?

So I'm pretty sure that there is a meaning in terms of the distribution of points, and probably what it means to be a 'face' on this surface.

Best Answer

Just like a planar graph: a graph that can be embedded in the plane such that its vertices are points of the plane and the edges can be "realised" as actual homeomorphic copies of $[0,1]$ (simple curves) that only intersect at vertices but nowhere else. Just as how you draw planar graphs. Now replace the plane by a surface and you have your definition. It says nothing on the distribution of the points (or size etc), but that we can topologically embed the graph (seen as a one-dimensional simplex) into the surface. For nice surfaces (differential or topological $2$-manifolds, really) we still have some analogue of the Jordan curve theorem, in the sense that a graph-cycle bounds some unique "interior", just as in the plane,so the notion of a "face" makes sense for such an embedding.

Related Question