The Book Thickness of 1-Planar Graphs is Constant

March 17, 2015 Β· Declared Dead Β· πŸ› Algorithmica

πŸ‘» CAUSE OF DEATH: Ghosted
No code link whatsoever

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Michael A. Bekos, Till Bruckdorfer, Michael Kaufmann, Chrysanthi N. Raftopoulou arXiv ID 1503.04990 Category cs.DS: Data Structures & Algorithms Cross-listed math.CO Citations 35 Venue Algorithmica Last Checked 3 months ago
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 is $O(\sqrt{n})$, where $n$ is the number of vertices of the graph.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

πŸ“œ Similar Papers

In the same crypt β€” Data Structures & Algorithms

Died the same way β€” πŸ‘» Ghosted