Lower bounds for the number of edge-crossings over the spine in a topological book embedding of a graph

DOI10.1016/S0166-218X(99)00044-XMaRDI QIDQ1304472zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Hikoe Enomoto, Miki Shimabara Miyauchi, Katsuhiro Ota

Publication date 9 April 2000

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0166-218x(99)00044-x

zbMATH Keywords

edge-crossingspagesspinetopological book imbedding

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Extremal problems in graph theory (05C35)

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.

Recommendations

• Embedding Graphs into a Three Page Book with O(m log n) Crossings of Edges over the Spine
• The book crossing number of a graph
• Graphs with E Edges Have Pagenumber O(√E)
• Optimum embedding of complete graphs in books

Cites work

• Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
• Embedding Graphs into a Three Page Book with O(m log n) Crossings of Edges over the Spine
• Embedding planar graphs in four pages
• On the pagenumber of complete bipartite graphs
• Pagenumber of complete bipartite graphs
• The book thickness of a graph

Cited in

(13)

• A survey on book-embedding of planar graphs
• Computing upward topological book embeddings of upward planar digraphs
• Approximating the fixed linear crossing number
• Crossing-Optimal Acyclic Hamiltonian Path Completion and Its Application to Upward Topological Book Embeddings
• Spine Crossing Minimization in Upward Topological Book Embeddings
• Embedding Graphs into a Three Page Book with O(m log n) Crossings of Edges over the Spine
• Upward book embeddings of st-graphs
• Computing Upward Topological Book Embeddings of Upward Planar Digraphs
• ON EMBEDDING A GRAPH ON TWO SETS OF POINTS
• Upward book embeddability of \(st\)-graphs: complexity and algorithms
• Book embeddings and crossing numbers
• Characterisations and examples of graph classes with bounded expansion
• Curve-constrained drawings of planar graphs

This page was built for publication: Lower bounds for the number of edge-crossings over the spine in a topological book embedding of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1304472)