Reconhecendo Grafos com até 1 Cruzamento
Abstract
The crossing number cr(G) of a graph G is the least number of crossings over all possible drawings of G. This paper describes a minor improvement over a naive algorithm for deciding if cr(G) ≤ 1.
References
Garey, M. R. and Johnson, D. S. (1983). Crossing number is NP-complete. SIAM Journal on Algebraic Discrete Methods, 4(3):312–316.
Grohe, M. (2001). Computing crossing numbers in quadratic time. In Proceedings of the Thirty-third Annual ACM Symposium on Theory of Computing, STOC ’01, pages 231–236, New York, NY, USA. ACM.
Hopcroft, J. and Tarjan, R. (1974). Efficient planarity testing. J. ACM, 21(4):549–568.
Leighton, F. T. (1983). Complexity Issues in VLSI: Optimal Layouts for the Shuffle-exchange Graph and Other Networks. MIT Press, Cambridge, MA, USA.
Purchase, H. (1997). Which aesthetic has the greatest effect on human understanding? In DiBattista, G., editor, Graph Drawing, volume 1353 of Lecture Notes in Computer Science, pages 248–261. Springer Berlin Heidelberg.
Székely, L. A. (1997). Crossing numbers and hard Erdős problems in discrete geometry. Combinatorics, Probability and Computing, 6:353–358.
Grohe, M. (2001). Computing crossing numbers in quadratic time. In Proceedings of the Thirty-third Annual ACM Symposium on Theory of Computing, STOC ’01, pages 231–236, New York, NY, USA. ACM.
Hopcroft, J. and Tarjan, R. (1974). Efficient planarity testing. J. ACM, 21(4):549–568.
Leighton, F. T. (1983). Complexity Issues in VLSI: Optimal Layouts for the Shuffle-exchange Graph and Other Networks. MIT Press, Cambridge, MA, USA.
Purchase, H. (1997). Which aesthetic has the greatest effect on human understanding? In DiBattista, G., editor, Graph Drawing, volume 1353 of Lecture Notes in Computer Science, pages 248–261. Springer Berlin Heidelberg.
Székely, L. A. (1997). Crossing numbers and hard Erdős problems in discrete geometry. Combinatorics, Probability and Computing, 6:353–358.
Published
2017-07-02
How to Cite
SILVA, André Carvalho; LEE, Orlando.
Reconhecendo Grafos com até 1 Cruzamento. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (ETC), 2. , 2017, São Paulo.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2017
.
p. 89-91.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2017.3199.
