Name
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 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 was O(root n), where n is the number of vertices of the graph. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/978-3-662-48350-3_12 | ALGORITHMS - ESA 2015 |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Computer science,Planar graph | Conference | 9294 |
ISSN | Citations | PageRank |
0302-9743 | 7 | 0.52 |
References | Authors | |
8 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael A. Bekos | 1 | 250 | 38.21 |
| Till Bruckdorfer | 2 | 33 | 5.50 |
| Michael Kaufmann 0001 | 3 | 41 | 8.28 |
| Chrysanthi N. Raftopoulou | 4 | 32 | 8.53 |