The crossing number of a graph on a compact 2-manifold (Q1352278)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: The crossing number of a graph on a compact 2-manifold |
scientific article; zbMATH DE number 977957
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The crossing number of a graph on a compact 2-manifold |
scientific article; zbMATH DE number 977957 |
Statements
The crossing number of a graph on a compact 2-manifold (English)
0 references
7 July 1997
0 references
The authors introduce a general framework for estimating crossing numbers of complete graphs on both orientable and nonorientable surfaces. These estimates are then used to estimate the crossing numbers for arbitrary graphs. The bounds are tight within a constant factor for many graphs, such as hypercubes, some complete graphs, and random graphs. Estimates are also given for related Turán graphs.
0 references
crossing numbers
0 references
surfaces
0 references
bounds
0 references
hypercubes
0 references
complete graphs
0 references
random graphs
0 references
Turán graphs
0 references
