Crossing numbers


The Crossing Number of the Complete Graph ★★★

Author(s):

The crossing number $ cr(G) $ of $ G $ is the minimum number of crossings in all drawings of $ G $ in the plane.

Conjecture   $ \displaystyle cr(K_n) =   \frac 14 \floor{\frac n2} \floor{\frac{n-1}2} \floor{\frac{n-2}2} \floor{\frac{n-3}2} $

Keywords: complete graph; crossing number

The Crossing Number of the Complete Bipartite Graph ★★★

Author(s): Turan

The crossing number $ cr(G) $ of $ G $ is the minimum number of crossings in all drawings of $ G $ in the plane.

Conjecture   $ \displaystyle   cr(K_{m,n}) = \floor{\frac m2} \floor{\frac {m-1}2}                      \floor{\frac n2} \floor{\frac {n-1}2}  $

Keywords: complete bipartite graph; crossing number

The Crossing Number of the Hypercube ★★

Author(s): Erdos; Guy

The crossing number $ cr(G) $ of $ G $ is the minimum number of crossings in all drawings of $ G $ in the plane.

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

Conjecture   $ \displaystyle \lim  \frac{cr(Q_d)}{4^d} = \frac{5}{32} $

Keywords: crossing number; hypercube

Drawing disconnected graphs on surfaces ★★

Author(s): DeVos; Mohar; Samal

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

Keywords: crossing number; surface

Crossing sequences ★★

Author(s): Archdeacon; Bonnington; Siran

Conjecture   Let $ (a_0,a_1,a_2,\ldots,0) $ be a sequence of nonnegative integers which strictly decreases until $ 0 $.

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

Keywords: crossing number; crossing sequence

Crossing numbers and coloring ★★★

Author(s): Albertson

We let $ cr(G) $ denote the crossing number of a graph $ G $.

Conjecture   Every graph $ G $ with $ \chi(G) \ge t $ satisfies $ cr(G) \ge cr(K_t) $.

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 $ G $? \[ \text{pair-cr}(G) = \text{cr}(G) \]

The crossing number $ \text{cr}(G) $ of a graph $ G $ is the minimum number of edge crossings in any drawing of $ G $ in the plane. In the pairwise crossing number $ \text{pair-cr}(G) $, we minimize the number of pairs of edges that cross.

Keywords: crossing number; pair-crossing number


Syndicate content