The Complexity of Several Realizability Problems for Abstract Topological Graphs

Kyncl, Jan (2008) The Complexity of Several Realizability Problems for Abstract Topological Graphs. In: Graph Drawing 15th International Symposium, GD 2007, September 24-26, 2007, Sydney, Australia , pp. 137-158 (Official URL:

Full text not available from this repository.


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
ID Code:834

Repository Staff Only: item control page


O. Aichholzer, F. Aurenhammer and H. Krasser, On the crossing number of complete graphs, Computing 76 (2006), no. 1-2, 165-176.

M. Chrobak and T. H. Payne, A linear-time algorithm for drawing a planar graph on a grid, Information Processing Letters 54 (1995), 241-246.

E. Gassner, M. Jünger, M. Percan, M. Schaefer and M. Schulz, Simultaneous graph embeddings with fixed edges, Graph-theoretic concepts in computer science, Lecture Notes in Computer Science 4271, 325-335, Springer, Berlin, 2006.

R.K. Guy, A combinatorial problem, Nabla (Bulletin of the Malayan Mathematical Society) 7 (1960), 68-72.

H. Harborth and I. Mengersen, Drawings of the complete graph with maximum number of crossings, Proceedings of the Twenty-third Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL,1992), Congressus Numerantium 88 (1992), 225-228.

J. Kratochvíl and J. Matousek, String graphs requiring exponential representations, Journal of Combinatorial Theory Ser. B 53 (1991), 1-4.

J. Kratochvíl, A. Lubiw and J. Nesetril, Noncrossing subgraphs in topological layouts, SIAM Journal on Discrete Mathematics 4 (1991), no. 2, 223-244.

J. Kratochvíl, String graphs. I. The number of critical nonstring graphs is infinite, Journal of Combinatorial Theory Ser. B 52 (1991), 53-66.

J. Kratochvíl, String graphs. II. Recognizing string graphs is NP-hard, Journal of Combinatorial Theory Ser. B 51 (1991), 67-78.

J. Kratochvíl, A special planar satisfiability problem and a consequence of its NP-completeness, Discrete Applied Mathematics 52 (1994), 233-252.

J. Kyncl, Enumeration of simple complete topological graphs, Electronic Notes in Discrete Mathematics 29 (2007), 295-299.

J. Kyncl and P. Valtr, On edges crossing few other edges in simple topological complete graphs, Graph Drawing 2005, Lecture Notes in Computer Science 3843, 274-284, Springer, Berlin, 2006.

J. Pach, J. Solymosi and G. Tóth, Unavoidable configurations in complete topological graphs, Discrete and Computational Geometry 30 (2003), 311-320.

J. Pach and G. Tóth, Recognizing string graphs is decidable, Discrete and computational geometry and graph drawing (Columbia, SC, 2001), Discrete and Computational Geometry 28 (2002), no. 4, 593-606.

J. Pach and G. Tóth, How many ways can one draw a graph?, Graph Drawing 2003, Lecture Notes in Computer Science 2912, 47-58, Springer, Berlin, 2004.

R. B. Richter and C. Thomassen, Relations between crossing numbers of complete and complete bipartite graphs, Amer. Math. Monthly 104 (1997), no. 2, 131--137.

M. Schaefer, E. Sedgwick and D. Stefankovic, Recognizing string graphs in NP, Journal of Computer and System Sciences 67 (2003), 365-380.

M. Schaefer and D. Stefankovic, Decidability of string graphs, Journal of Computer and System Sciences 68 (2004), 319-334.

F. Shahrokhi, L. A. Székely and I. Vrt'o, Crossing Numbers of Graphs, Lower Bound Techniques and Algorithms: A Survey, Proc. DIMACS Workshop on Graph Drawing'94, Lecture Notes in Computer Science 894, 131-142, Springer, Berlin, 1995.

U. Wagner, On the rectilinear crossing number of complete graphs, Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore, MD, 2003), 583-588, ACM, New York, 2003.