The Book Embedding Problem from a SAT-Solving Perspective

Bekos, Michael A. and Kaufmann, Michael and Zielke, Christian (2015) The Book Embedding Problem from a SAT-Solving Perspective. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 24-26, 2015 , pp. 125-138(Official URL:

Full text not available from this repository.


In a book embedding, the vertices of a graph are placed on the spine of a book and the edges are assigned to pages, so that edges of the same page do not cross. In this paper, we approach the problem of determining whether a graph can be embedded in a book of a certain number of pages from a different perspective: We propose a simple and quite intuitive SAT formulation, which is robust enough to solve non-trivial instances of the problem in reasonable time. As a byproduct, we show a lower bound of 4 on the page number of 1-planar graphs.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.490 Embeddings
M Methods > M.999 Others
P Styles > P.999 Others

Actions (login required)

View Item View Item