The Book Thickness of 1-Planar Graphs is Constant

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 th...

Full description

Saved in:
Bibliographic Details
Published in:Algorithmica 2017-10, Vol.79 (2), p.444-465
Main Authors: Bekos, Michael A., Bruckdorfer, Till, Kaufmann, Michael, Raftopoulou, Chrysanthi N.
Format: Article
Language:English
Subjects:
Algorithm Analysis and Problem Complexity
Algorithms
Computer Science
Computer Systems Organization and Communication Networks
Data Structures and Information Theory
Graph theory
Mathematics of Computing
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0178-4617
1432-0541
DOI:10.1007/s00453-016-0203-2