Publication at Faculty of Mathematics and Physics |
2011
Abstract
An abstract topological graph (briefly an AT-graph) is a pair A=(G,R) where G=(V,E) is a graph and R is a set of pairs of its edges. An AT-graph A is simply realizable if G can be drawn in the plane in such a way that each pair of edges from R crosses exactly once and no other pair crosses.
We present a polynomial algorithm which decides whether a given complete AT-graph is simply realizable. On the other hand, we show that other similar realizability problems for (complete) AT-graphs are NP-hard.