The complexity of several realizability problems for abstract topological graphs

Abstract

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.

Keywords

• complexity
• several
• realizability
• problems
• abstract
• topological
• graphs