Svenja Griesbach
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Svenja Griesbach has a total of 5 co-authors. Here are the top co-authors by number of shared publications:
- Chrysanthi N. Raftopoulou
NTUA, Sch Appl Math & Phys Sci, Athens, Greece
1 shared publication - Fabrizio Montecchiani
University of Perugia, Perugia, Italy
1 shared publication - Giordano Da Lozzo
Roma Tre University, Rome, Italy
1 shared publication - Martin Gronemann
Department of Mathematics and Computer Science University of Cologne Germany
1 shared publication - Michael A. Bekos
University of Ioannina
1 shared publication
Latest Publications
- Open Access
Book Embeddings of Nonplanar Graphs with Small Faces in Few Pages
An embedding of a graph in a book, called book embedding, consists of a linear ordering of its vertices along the spine of the book and an assignment of its edges to the pages of the book, so that no two edges on the same page cross. The book thickness of a graph is the minimum number of pages over all its book embeddings. For planar graphs, a fundamental result is due to Yannakakis, who proposed an algorithm to compute embeddings of planar graphs in books with four pages. Our main contribution is a technique that generalizes this result to a much wider family of nonplanar graphs, which is characterized by a biconnected skeleton of crossing-free edges whose faces have bounded degree. Notably, this family includes all 1-planar, all optimal 2-planar, and all k-map (with bounded k) graphs as subgraphs. We prove that this family of graphs has bounded book thickness, and as a corollary, we obtain the first constant upper bound for the book thickness of optimal 2-planar and k-map graphs.
Open AccessBook Embeddings of Nonplanar Graphs with Small Faces in Few Pages
An embedding of a graph in a book, called book embedding, consists of a linear ordering of its vertices along the spine of the book and an assignment of its edges to the pages of the book, so that no two edges on the same page cross. The book thickness of a graph is the minimum number of pages over all its book embeddings. For planar graphs, a fundamental result is due to Yannakakis, who proposed an algorithm to compute embeddings of planar graphs in books with four pages. Our main contribution is a technique that generalizes this result to a much wider family of nonplanar graphs, which is characterized by a biconnected skeleton of crossing-free edges whose faces have bounded degree. Notably, this family includes all 1-planar, all optimal 2-planar, and all k-map (with bounded k) graphs as subgraphs. We prove that this family of graphs has bounded book thickness, and as a corollary, we obtain the first constant upper bound for the book thickness of optimal 2-planar and k-map graphs.