The Complexity of Several Realizability Problems for Abstract Topological Graphs

Kynčl, Jan (2008) The Complexity of Several Realizability Problems for Abstract Topological Graphs. In: Graph Drawing 15th International Symposium, GD 2007, September 24-26, 2007 , pp. 137-158(Official URL: http://dx.doi.org/10.1007/978-3-540-77537-9_16).

Full text not available from this repository.

Abstract

An $abstract topological graph$ (briefly an $AT-graph$) is a pair $A=(G,R)$ where $G=(V,E)$ is a graph and $Rsubseteq E choose 2$ 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.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-77537-9_16
Classifications: Z Theory > Z.750 Topology
G Algorithms and Complexity > G.490 Embeddings
URI: http://gdea.informatik.uni-koeln.de/id/eprint/834

Actions (login required)

View Item View Item