Lower bounds for the number of edge-crossings over the spine in a topological book embedding of a graph (Q1304472): Difference between revisions
From MaRDI portal
Created a new Item |
Created claim: Wikidata QID (P12): Q56689187, #quickstatements; #temporary_batch_1705750702424 |
||
| Property / Wikidata QID | |||
| Property / Wikidata QID: Q56689187 / rank | |||
Normal rank | |||
Revision as of 12:38, 20 January 2024
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
