A trade-off between page number and page width of book embeddings of graphs
type: Item
instance of: scholarly article
title: A trade-off between page number and page width of book embeddings of graphs
zbMATH Open document ID: 0673.05023
DOI: 10.1016/0890-5401(88)90036-3
published in: Information and Computation
publication date: 1988-01-01T00:00:00Z
review text: The author proves that for any integer \(n\geq 3\) there is a family of graphs \(G_{n,k}\), \(k=1,2,..\). such that (1) each \(G_{n,k}\) admits an embedding in a book with n pages, (2) any family of n-page embeddings of the \(G_{n,k}\) has unbounded page width \((=\) maximum number of edges intersecting any perpendicular line to the spine of any page), and (3) there are \((n+1)\)-page embeddings of the \(G_{n,k}'s\) whose page widths are bounded by a constant.
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 4101208
zbMATH Keywords: book embeddings
zbMATH Keywords: page number
zbMATH Keywords: page width
Wikidata QID: Q56689182
author: Elena Stöhr
reviewed by: Jozef Širáň
MaRDI profile type: Publication
full work available at URL: 0890-5401(88)90036-3
OpenAlex ID: W2046540463
cites work: The book thickness of a graph
cites work: Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
cites work: Embedding Outerplanar Graphs in Small Books
cites work: The pagenumber of genus g graphs is O( g )
cites work: Q3780900
DBLP publication ID: journals/iandc/Stohr88
description: scientific article; zbMATH DE number 4101208