Logo

Login | Create Account

Crossing Number of Abstract Topological Graphs

Kratochvíl, Jan (1998) Crossing Number of Abstract Topological Graphs. [Conference Paper]

Full text not available from this repository.

Abstract

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
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
ID Code:246
Deposited By:Arnopolina, Galina
Deposited On:09 Nov 2004
Last Modified:18 Sep 2008 13:08
Alternative Locations:http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=1547&spage=238

Repository Staff Only: item control page

References

1. M.R. Garey and D.S. Johnson. Crossing number is np-complete, SIAM J. Algebraic and Discrete Methods 4(1983), 312-316.

2. M.C. Golumbic. Algorithmic graph theory and perfect graphs, Acad. Pr., NY, 1980.

3. Kratochvíl, J.: String graphs II. Recognizing string graphs is NP-hard, J. Combin. Theory Ser. B 52 (1991), 67-78.

4. J. Kratochví, A. Lubiw, and J. Nesetril. Noncrossing subgraphs of topological layouts, SIAM J. Discrete Math. 4 (1991), 223-244.

5. J. Kratochvíl, J. Matousek. String graphs requiringexponential representations. J. Combin. Theory Ser. B 53 (1991), 1-4.

6. F. Sharokhi, O. Sýkora, and I. Vrto. Crossing number of graphs, lower bound techniques and algorithms: a survey, in: R. Tamassia and I.G. Tollis, editors, Graph Drawing (Proc. GD '94), LNCS, 894, Springer-Verlag, pages 131-142, 1995.

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.