Lower bounds for the number of edge-crossings over the spine in a topological book embedding of a graph (Q1304472)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Lower bounds for the number of edge-crossings over the spine in a topological book embedding of a graph |
scientific article |
Statements
Lower bounds for the number of edge-crossings over the spine in a topological book embedding of a graph (English)
0 references
9 April 2000
0 references
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.
0 references
topological book imbedding
0 references
pages
0 references
spine
0 references
edge-crossings
0 references
0 references