Simple realizability of complete abstract topological graphs simplified

Abstrakt

An abstract topological graph (briefly an AT-graph) is a pair A=(G,X) where G=(V,E) is a graph and X 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 characterize simply realizable complete AT-graphs 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.

Klíčová slova

• simple complete topological graph
• weak isomorphism of topological graphs
• abstract topological graph
• simple realizability of abstract topological graphs
• homotopy class