# Crossing numbers

## The Crossing Number of the Complete Graph ★★★

Author(s):

The crossing number of is the minimum number of crossings in all drawings of in the plane.

Conjecture Keywords: complete graph; crossing number

## The Crossing Number of the Complete Bipartite Graph ★★★

Author(s): Turan

The crossing number of is the minimum number of crossings in all drawings of in the plane.

Conjecture Keywords: complete bipartite graph; crossing number

## The Crossing Number of the Hypercube ★★

Author(s): Erdos; Guy

The crossing number of is the minimum number of crossings in all drawings of in the plane.

The -dimensional (hyper)cube is the graph whose vertices are all binary sequences of length , and two of the sequences are adjacent in if they differ in precisely one coordinate.

Conjecture Keywords: crossing number; hypercube

## Drawing disconnected graphs on surfaces ★★

Author(s): DeVos; Mohar; Samal

Conjecture   Let be the disjoint union of the graphs and and let be a surface. Is it true that every optimal drawing of on has the property that and are disjoint?

Keywords: crossing number; surface

## Crossing sequences ★★

Author(s): Archdeacon; Bonnington; Siran

Conjecture   Let be a sequence of nonnegative integers which strictly decreases until .

Then there exists a graph that be drawn on a surface with orientable (nonorientable, resp.) genus with crossings, but not with less crossings.

Keywords: crossing number; crossing sequence

## Crossing numbers and coloring ★★★

Author(s): Albertson

We let denote the crossing number of a graph .

Conjecture   Every graph with satisfies .

Keywords: coloring; complete graph; crossing number

## Are different notions of the crossing number the same? ★★★

Author(s): Pach; Tóth

Problem   Does the following equality hold for every graph ? The crossing number of a graph is the minimum number of edge crossings in any drawing of in the plane. In the pairwise crossing number , we minimize the number of pairs of edges that cross.

Keywords: crossing number; pair-crossing number 