Reconhecendo Grafos com até 1 Cruzamento
Resumo
O número de cruzamentos de um grafo G é o menor número de cruzamentos dentre todos os desenhos de G. Este artigo descreve uma pequena melhora para um algoritmo ingênuo para decidir se cr(G) ≤ 1.
Referências
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.
Publicado
02/07/2017
Como Citar
SILVA, André Carvalho; LEE, Orlando.
Reconhecendo Grafos com até 1 Cruzamento. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (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.
