Special numbers of crossings for complete graphs (Q1349080)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Special numbers of crossings for complete graphs |
scientific article |
Statements
Special numbers of crossings for complete graphs (English)
0 references
21 May 2002
0 references
The paper studies a variant of the crossing number problem for complete graphs, where the graph drawing is restricted to cycle drawings. In a cycle drawing the vertices span a strictly convex polygon, and every edge is drawn completely inside or outside the polygon. It is shown that \(K_{14}\) can be drawn with 953 crossings, but it has more crossings in any cycle drawing. Up to \(n= 7\) it makes no difference on the crossing numbers of complete graphs if we require cycle drawings. It is conjectured that \(n=14\) is the smallest value where these crossing numbers differ.
0 references
crossing number
0 references
complete graphs
0 references
graph drawing
0 references