Logo

Login

The Complexity of Several Realizability Problems for Abstract Topological Graphs

Kyncl, Jan (2008) The Complexity of Several Realizability Problems for Abstract Topological Graphs. [Conference Paper]

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
Classifications:Z Theory > Z.750 Topology
G Algorithms and Complexity > G.490 Embeddings
ID Code:834
Deposited By:GDEA, Administration
Deposited On:24 Jun 2008
Last Modified:25 Jan 2010 10:44
Alternative Locations:http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=4875&spage=137

Repository Staff Only: item control page

References

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

2. 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.

3. 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.

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

5. 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.

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

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

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

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

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

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

12. 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.

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

14. 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.

15. 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.

16. 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.

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

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

19. 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.

20. 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.

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.