Geodesic
Parameterized Algorithms for Book Embedding Problems
Journal of Graph Algorithms and Applications, Special issue on Selected papers from the Twenty-seventh International Symposium on Graph Drawing and Network Visualization, GD 2019 , Tome 24 (2020) no. 4, pp. 603-620.

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

A $k$-page book embedding of a graph $G$ draws the vertices of $G$ on a line and the edges on $k$ half-planes (called pages) bounded by this line, such that no two edges on the same page cross. We study the problem of determining whether $G$ admits a $k$-page book embedding both when the linear order of the vertices is fixed, called ${\rm F{\small IXED}-O{\small RDER}~B{\small OOK}~T{\small HICKNESS}}$, or not fixed, called ${\rm B{\small OOK}~T{\small HICKNESS}}$. Both problems are known to be ${\sf NP}$-complete in general. We show that ${\rm F{\small IXED}-O{\small RDER}~B{\small OOK}~T{\small HICKNESS}}$ and ${\rm B{\small OOK}~T{\small HICKNESS}}$ are fixed-parameter tractable parameterized by the vertex cover number of the graph and that ${\rm F{\small IXED}-O{\small RDER}~B{\small OOK}~T{\small HICKNESS}}$ is fixed-parameter tractable parameterized by the pathwidth of the vertex order.
DOI : 10.7155/jgaa.00526
Keywords: graph drawing, book embedding, book thickness, parameterized algorithms, pathwidth, vertex cover number 
@article{JGAA_2020_24_4_a3,
     author = {Sujoy Bhore and Robert Ganian and Fabrizio Montecchiani and Martin N\"ollenburg},
     title = {Parameterized {Algorithms} for {Book} {Embedding} {Problems}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {603--620},
     publisher = {mathdoc},
     volume = {24},
     number = {4},
     year = {2020},
     doi = {10.7155/jgaa.00526},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00526/}
}
TY  - JOUR
AU  - Sujoy Bhore
AU  - Robert Ganian
AU  - Fabrizio Montecchiani
AU  - Martin Nöllenburg
TI  - Parameterized Algorithms for Book Embedding Problems
JO  - Journal of Graph Algorithms and Applications
PY  - 2020
SP  - 603
EP  - 620
VL  - 24
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00526/
DO  - 10.7155/jgaa.00526
LA  - en
ID  - JGAA_2020_24_4_a3
ER  - 
%0 Journal Article
%A Sujoy Bhore
%A Robert Ganian
%A Fabrizio Montecchiani
%A Martin Nöllenburg
%T Parameterized Algorithms for Book Embedding Problems
%J Journal of Graph Algorithms and Applications
%D 2020
%P 603-620
%V 24
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00526/
%R 10.7155/jgaa.00526
%G en
%F JGAA_2020_24_4_a3
Sujoy Bhore; Robert Ganian; Fabrizio Montecchiani; Martin Nöllenburg. Parameterized Algorithms for Book Embedding Problems. Journal of Graph Algorithms and Applications, 
							Special issue on Selected papers from the Twenty-seventh International Symposium on Graph Drawing and Network Visualization, GD 2019
					, Tome 24 (2020) no. 4, pp. 603-620. doi : 10.7155/jgaa.00526. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00526/

Cité par Sources :