Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

The complexity of computing the cylindrical and the t-circle crossing number of a graph

Autor(es):
Duque, Frank [1] ; Gonzalez-Aguilar, Hernan [2] ; Hernadez-Velez, Cesar [2] ; Leanos, Jesus [3] ; Medina, Carolina [4]
Número total de Autores: 5
Afiliação do(s) autor(es):
[1] Univ Antioquia, Inst Matemat, Medellin 050010 - Colombia
[2] Univ Autonoma San Luis Potosi, Fac Ciencias, San Luis Potosi 78290 - Mexico
[3] Univ Autonoma Zacatecas, Unidad Acad Matemat, Zacatecas 9800 - Mexico
[4] Univ Autonoma San Luis Potosi, Inst Fis, San Luis Potosi 78290 - Mexico
Número total de Afiliações: 4
Tipo de documento: Artigo Científico
Fonte: ELECTRONIC JOURNAL OF COMBINATORICS; v. 25, n. 2 JUN 8 2018.
Citações Web of Science: 1
Resumo

A plane drawing of a graph is cylindrical if there exist two concentric circles that contain all the vertices of the graph, and no edge intersects (other than at its endpoints) any of these circles. The cylindrical crossing number of a graph G is the minimum number of crossings in a cylindrical drawing of G. In his influential survey on the variants of the definition of the crossing number of a graph, Schaefer lists the complexity of computing the cylindrical crossing number of a graph as an open question. In this paper, we prove that the problem of deciding whether a given graph admits a cylindrical embedding is NP-complete, and as a consequence we show that the t-cylindrical crossing number problem is also NP-complete. Moreover, we show an analogous result for the natural generalization of the cylindrical crossing number, namely the t-circle crossing number. (AU)

Processo FAPESP: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
Beneficiário:Carlos Eduardo Ferreira
Linha de fomento: Auxílio à Pesquisa - Temático