An abstract topological graph (briefly an AT-graph) is a pair $A=(G,\mathcal{ X})$ where $G=(V,E)$ is a graph and $\mathcal{ X}\subseteq { E \choose 2}$ is a set of pairs of its edges. The AT-graph $A$ is simply realizable if $G$ can be drawn in the plane so that each pair of edges from $\mathcal{ X}$ crosses exactly once and no other pair crosses. We show that simply realizable complete AT-graphs are characterized by a finite set of forbidden AT-subgraphs, each with at most six vertices. This implies a straightforward polynomial algorithm for testing simple realizability of complete AT-graphs, which simplifies a previous algorithm by the author. We also show an analogous result for independent $\mathbb{ Z}_2$-realizability, where only the parity of the number of crossings for each pair of independent edges is specified.
Categories: math.CO cs.DM