The crossing number of a graph on a compact 2-manifold (Q1352278)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The crossing number of a graph on a compact 2-manifold |
scientific article |
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
