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.