Crossing numbers

Graph Theory » Topological G.T. » 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

Posted by Robert Samal
updated July 28th, 2008

3 comments

Graph Theory » Topological G.T. » Crossing numbers

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

Posted by Robert Samal
updated May 11th, 2007

add new comment

Graph Theory » Topological G.T. » Crossing numbers

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

Posted by Robert Samal
updated July 18th, 2008

1 comment

Graph Theory » Topological G.T. » Crossing numbers

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

Posted by mdevos
updated September 30th, 2007

1 comment

Graph Theory » Topological G.T. » Crossing numbers

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

Posted by Robert Samal
updated July 30th, 2008

add new comment

Graph Theory » Topological G.T. » Crossing numbers