2015/03/17 by Bekos, Michael A., Bruckdorfer, Till, Kaufmann, Michael +1
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1503.04990
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 on the same page do not cross. In this paper, we prove that every 1-planar graph (that is, a graph that can be drawn on the plane such that no edge is crossed more than once) admits an embedding in a book with constant number of pages. To the best of our knowledge, the best non-trivial previous upper-bound is O(√(n)), where n is the number of vertices of the graph.