Crossing Number of Abstract Topological Graphs

Kratochvíl, Jan (1998) Crossing Number of Abstract Topological Graphs. In: Graph Drawing 6th International Symposium, GD’ 98, August 13-15, 1998 , pp. 238-245(Official URL:

Full text not available from this repository.


We revoke the problem of drawing graphs in the plane so that only certain specified pairs of edges are allowed to cross. We overview some previous results and open problems, namely the connection to intersection graphs of curves in the plane. We complement these by stating a new conjecture and showing that its proof would solve the problem of algorithmic decidability of recognition of string graphs as well as realizability of topological graphs and feasible drawability of graphs with restricted edge crossings.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-37623-2_18
Classifications: Z Theory > Z.999 Others
Z Theory > Z.750 Topology
G Algorithms and Complexity > G.999 Others
G Algorithms and Complexity > G.420 Crossings

Actions (login required)

View Item View Item