Geodesic
The complexity of computing the cylindrical and the \(t\)-circle crossing number of a graph
Frank Duque1 ; Hernán González-Aguilar2 ; César Hernández-Vélez2 ; Jesús Leaños3 ; Carolina Medina2
1Universidad de Antioquia
2Universidad Autónoma de San Luis Potosí
3Universidad Autónoma de Zacatecas
The electronic journal of combinatorics, Tome 25 (2018) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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\)-crossing number.
DOI : 10.37236/7193
Classification : 05C10, 68Q25, 05C85
Mots-clés : cylindrical crossing number, book crossing number, \(t\)-circle crossing number

Frank Duque  1   ; Hernán González-Aguilar  2   ; César Hernández-Vélez  2   ; Jesús Leaños  3   ; Carolina Medina  2

1 Universidad de Antioquia
2 Universidad Autónoma de San Luis Potosí
3 Universidad Autónoma de Zacatecas 
@article{10_37236_7193,
     author = {Frank Duque and Hern\'an Gonz\'alez-Aguilar and C\'esar Hern\'andez-V\'elez and Jes\'us Lea\~nos and Carolina Medina},
     title = {The complexity of computing the cylindrical and the \(t\)-circle crossing number of a graph},
     journal = {The electronic journal of combinatorics},
     year = {2018},
     volume = {25},
     number = {2},
     doi = {10.37236/7193},
     zbl = {1388.05046},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/7193/}
}
TY  - JOUR
AU  - Frank Duque
AU  - Hernán González-Aguilar
AU  - César Hernández-Vélez
AU  - Jesús Leaños
AU  - Carolina Medina
TI  - The complexity of computing the cylindrical and the \(t\)-circle crossing number of a graph
JO  - The electronic journal of combinatorics
PY  - 2018
VL  - 25
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/7193/
DO  - 10.37236/7193
ID  - 10_37236_7193
ER  - 
%0 Journal Article
%A Frank Duque
%A Hernán González-Aguilar
%A César Hernández-Vélez
%A Jesús Leaños
%A Carolina Medina
%T The complexity of computing the cylindrical and the \(t\)-circle crossing number of a graph
%J The electronic journal of combinatorics
%D 2018
%V 25
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/7193/
%R 10.37236/7193
%F 10_37236_7193
Frank Duque; Hernán González-Aguilar; César Hernández-Vélez; Jesús Leaños; Carolina Medina. The complexity of computing the cylindrical and the \(t\)-circle crossing number of a graph. The electronic journal of combinatorics, Tome 25 (2018) no. 2. doi: 10.37236/7193

Cité par Sources :