The crossing number of a graph on a compact 2-manifold (Q1352278): Difference between revisions
From MaRDI portal
Removed claims |
Set OpenAlex properties. |
||
| (2 intermediate revisions by 2 users not shown) | |||
| Property / author | |||
| Property / author: László A. Székely / rank | |||
Normal rank | |||
| Property / author | |||
| Property / author: Imrich Vrt'o / rank | |||
Normal rank | |||
| Property / reviewed by | |||
| Property / reviewed by: Arthur T. White / rank | |||
Normal rank | |||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W1986870886 / rank | |||
Normal rank | |||
Latest revision as of 19:02, 19 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
