Geodesic
Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth
Journal of Graph Algorithms and Applications, Tome 22 (2018) no. 4, pp. 577-606.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

We investigate crossing minimization for $1$-page and $2$-page book drawings. We show that computing the $1$-page crossing number is fixed-parameter tractable with respect to the number of crossings, that testing $2$-page planarity is fixed-parameter tractable with respect to treewidth, and that computing the $2$-page crossing number is fixed-parameter tractable with respect to the sum of the number of crossings and the treewidth of the input graph. We prove these results via Courcelle's theorem on the fixed-parameter tractability of properties expressible in monadic second order logic for graphs of bounded treewidth. 
@article{JGAA_2018_22_4_a1,
     author = {Michael Bannister and David Eppstein},
     title = {Crossing {Minimization} for 1-page and 2-page {Drawings} of {Graphs} with {Bounded} {Treewidth}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {577--606},
     publisher = {mathdoc},
     volume = {22},
     number = {4},
     year = {2018},
     doi = {10.7155/jgaa.00479},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00479/}
}
TY  - JOUR
AU  - Michael Bannister
AU  - David Eppstein
TI  - Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth
JO  - Journal of Graph Algorithms and Applications
PY  - 2018
SP  - 577
EP  - 606
VL  - 22
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00479/
DO  - 10.7155/jgaa.00479
LA  - en
ID  - JGAA_2018_22_4_a1
ER  - 
%0 Journal Article
%A Michael Bannister
%A David Eppstein
%T Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth
%J Journal of Graph Algorithms and Applications
%D 2018
%P 577-606
%V 22
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00479/
%R 10.7155/jgaa.00479
%G en
%F JGAA_2018_22_4_a1
Michael Bannister; David Eppstein. Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth. Journal of Graph Algorithms and Applications, Tome 22 (2018) no. 4, pp. 577-606. doi : 10.7155/jgaa.00479. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00479/

Cité par Sources :