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: http://dx.doi.org/10.1007/978-3-319-27261-0_11).

Full text not available from this repository.

Abstract

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
Divisions: UNSPECIFIED
Depositing User: Administration GDEA
Date Deposited: 04 May 2016 16:16
Last Modified: 23 Jun 2016 08:50
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1483

Actions (login required)

View Item View Item