Embedding Graphs Containing \(K_5\)-Subdivisions

Abstract

Given a non-planar graph \(G\) with a subdivision of \(K_5\) as a subgraph, we can either transform the \(K_5\)-subdivision into a \(K_{3,3}\)-subdivision if it is possible, or else we obtain a partition of the vertices of \(G\backslash K_5\) into equivalence classes. As a result, we can reduce a projective planarity or toroidality algorithm to a small constant number of simple planarity checks [6] or to a \(K_{3,3}\)-subdivision in the graph \(G\). It significantly simplifies algorithms presented in [7], [10], and [12]. We then need to consider only the embeddings on the given surface of a \(K_{3,3}\)-subdivision, which are much less numerous than those of \(K_5\).