The crossing number of a graph on a compact 2-manifold (Q1352278): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Revision as of 03:01, 5 March 2024
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
