Embeddings of graphs (Q1313840)

The author surveys some recent results about graphs embedded on higher surfaces or in general topological spaces. He begins by examining the relationship between the Jordan Curve Theorem and Kuratowski's Theorem. In particular, he discusses his result that in an arbitrary arcwise connected Hausdorff space which is not a simple closed curve and in which no simple arc separates, every simple closed curve separates if and only if neither \(K_{3,3}\) nor \(K_ 5\) embeds in that space. Roughly speaking, the Jordan Curve Theorem is equivalent to the easy part of Kuratowski's Theorem. He also discusses several similar results related to the Jordan-Schönflies Theorem. After an introduction to combinatorial embeddings, the author examines the computational complexity of embeddings, including his two recent proofs that the graph genus problem is NP-complete. There are various ways of measuring the local planarity of an embedded graph. The author surveys these measures and shows how embedded graphs which are sufficiently locally planar share properties with planar graphs, such as being genus embeddings and being unique if the graph is 3-connected. He then mentions several applications to computational complexity. The paper closes with an examination of symmetries of surfaces. Included is the theorem that there are only finitely many vertex-transitive graphs of a given genus \(g\geq 3\).