Kyncl, Jan2020-05-162020-05-162020-05-162020-05-0410.1007/s00454-020-00204-0https://infoscience.epfl.ch/handle/20.500.14299/168776WOS:000530185900001An abstract topological graph (briefly an AT-graph) is a pair A = (G, X) where G = (V, E) is a graph and X. E2 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 X crosses exactly once and no other pair crosses. We showthat 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 Z2-realizability, where only the parity of the number of crossings for each pair of independent edges is specified.Computer Science, Theory & MethodsMathematicsComputer Scienceabstract topological graphrotation systemsimple realizabilitycomplete graphindependent z(2)-realizabilitycrossing numberstext::journal::journal article::research article