Lower bounds for the number of edge-crossings over the spine in a topological book embedding of a graph
type: Item
instance of: scholarly article
title: Lower bounds for the number of edge-crossings over the spine in a topological book embedding of a graph
zbMATH Open document ID: 0933.05042
DOI: 10.1016/S0166-218X(99)00044-X
author: Hikoe Enomoto
author: Miki Shimabara Miyauchi
author: Katsuhiro Ota
published in: Discrete Applied Mathematics
publication date: 2000-04-09T00:00:00Z
review text: A topological book imbedding of a graph places the vertices along the spine and the edges in the pages; edges are allowed to cross the spine. Enomoto and Miyauchi (preprint) showed that every graph of order \(n\) and size \(m\) can be imbedded into a 3-page book with at most \(O(m\log n)\) edge-crossings over the spine. The present paper gives lower bounds on the number of edge-crossings over the spine which show that the bound \(O(m\log n)\) is essentially best possible.
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1339914
zbMATH Keywords: topological book imbedding
zbMATH Keywords: pages
zbMATH Keywords: spine
zbMATH Keywords: edge-crossings
Wikidata QID: Q56689187
reviewed by: Arthur T. White
MaRDI profile type: Publication
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 Graphs into a Three Page Book with O(m log n) Crossings of Edges over the Spine
cites work: On the pagenumber of complete bipartite graphs
cites work: Pagenumber of complete bipartite graphs
cites work: Embedding planar graphs in four pages
full work available at URL: s0166-218x(99)00044-x
OpenAlex ID: W2009528969
DBLP publication ID: journals/dam/EnomotoMO99
description: scientific article; zbMATH DE number 1339914