Neil Robertson

Flexibility of polyhedral embeddings of graphs on a surface

Abstract for the joint Combinatorics and Geometry/Topology Seminars
April 22, 1999 at 2:50

The following theorem has been established in joint work with Bojan Mohar. Given a surface S, there is an integer f(S) such that any 3-connected graph G admits at most f(S) combinatorially distinct 3-representative embeddings into S. In such an embedding all the facial boundaries are simple cycles, and distinct facial cycles meet at most in an edge or vertex. Two such embeddings of G are distinct if their facial cycles differ. Thus, for the 2-sphere f(S) = 1, but already the 7-clique has 60 3-representative embeddings on the torus. This talk will discuss the proof of the theorem.