Keywords (1)

Academic
Publications
Simple Realizability of Complete Abstract Topological Graphs in P

Simple Realizability of Complete Abstract Topological Graphs in P,10.1007/s00454-010-9320-x,Discrete & Computational Geometry,Jan Kyncl

Simple Realizability of Complete Abstract Topological Graphs in P  
BibTex | RIS | RefWorks Download
An abstract topological graph (briefly an AT-graph) is a pair where G=(V,E) is a graph and 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 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.
Journal: Discrete & Computational Geometry - DCG , vol. 45, no. 3, pp. 383-399, 2011
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.