2015/10/20 by Md. Jawaherul Alam, Alam, Md. Jawaherul, Franz J. Brandenburg +3
Computer Science · Engineering · #Advanced Graph Theory Research #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Structural Analysis and Optimization
paper · pdf · doi:10.48550/arxiv.1510.05891
openalex publication_date 2015/10/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In a book embedding of a graph G, the vertices of G are placed in order along a straight-line called spine of the book, and the edges of G are drawn on a set of half-planes, called the pages of the book, such that two edges drawn on a page do not cross each other. The minimum number of pages in which a graph can be embedded is called the book-thickness or the page-number of the graph. It is known that every planar graph has a book embedding on at most four pages. Here we investigate the book-embeddings of 1-planar graphs. A graph is 1-planar if it can be drawn in the plane such that each edge is crossed at most once. We prove that every 1-planar graph has a book embedding on at most 16 pages and every 3-connected 1-planar graph has a book embedding on at most 12 pages. The drawings can be computed in linear time from any given 1-planar embedding of the graph.