Embedding Graphs Containing $K_5$-Subdivisions on the Torus

Abstract

We simplify and further develop the methods and ideas of [A. Gagarin, W. Kocay, “Embedding graphs containing $K_5$-subdivisions,” Ars Combin. 64 (2002), pp. 33-49] to efficiently test embeddability of graphs on the torus. Given a non-planar graph $G$ containing a $K_5$-subdivision subgraph, we show that it is possible either to transform the $K_5$-subdivision into a certain type of $K_{3,3}$-subdivision, or else to reduce the toroidality testing problem for $G$ to a small constant number of planarity checks and, eventually, rearrangements of planar embeddings. It is shown how to consider efficiently only one $K_5$-subdivision in the input graph $G$ to decide whether $G$ is embeddable on the torus. This makes it possible to detect a bigger class of toroidal and non-toroidal graphs.