A book embedding of a graph $G$ is an embedding of $G$ on a collection of half-planes (called pages) having the same line (called spine) as their boundary, such that the vertices all lie on the spine and there are no crossing edges. The book thickness of a graph $G$ is the smallest number of pages over all book embeddings of $G$.
book thickness is also known as page number, stack number and fixed outer-thickness.
Minimal/maximal is with respect to the contents of ISGCI. Only references for direct bounds are given. Where no reference is given, check equivalent parameters.
Problems in italics have no summary page and are only listed when ISGCI contains a result for the current parameter.
3-Colourability
[?]
|
Unknown to ISGCI | [+]Details | |||||
Clique
[?]
|
XP | [+]Details | |||||
Clique cover
[?]
|
Unknown to ISGCI | [+]Details | |||||
Colourability
[?]
|
Unknown to ISGCI | [+]Details | |||||
Domination
[?]
|
Unknown to ISGCI | [+]Details | |||||
Feedback vertex set
[?]
|
Unknown to ISGCI | [+]Details | |||||
Graph isomorphism
[?]
|
Unknown to ISGCI | [+]Details | |||||
Hamiltonian cycle
[?]
|
Unknown to ISGCI | [+]Details | |||||
Hamiltonian path
[?]
|
Unknown to ISGCI | [+]Details | |||||
Independent set
[?]
|
Unknown to ISGCI | [+]Details | |||||
Maximum cut
[?]
(decision variant)
|
Unknown to ISGCI | [+]Details | |||||
Monopolarity
[?]
|
Unknown to ISGCI | [+]Details | |||||
Polarity
[?]
|
Unknown to ISGCI | [+]Details | |||||
Weighted clique
[?]
|
XP | [+]Details | |||||
Weighted feedback vertex set
[?]
|
Unknown to ISGCI | [+]Details | |||||
Weighted independent set
[?]
|
Unknown to ISGCI | [+]Details |