An abstract topological graph (briefly an AT-graph) is a pair where is a graph and $\subseteq {E \choose 2}A$ is simply realizable if can be drawn in the plane so that each pair of edges from 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 -realizability, where only the parity of the number of crossings for each pair of independent edges is specified.

生成讲解博客的中文版本

生成AI智能校验的中文版本