Lower bounds for the number of edge-crossings over the spine in a topological book embedding of a graph (Q1304472): Difference between revisions

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.