Open Problem Garden

Importance: Medium ✭✭

Author(s):	Archdeacon, Dan
	Bonnington, C. Paul
	Siran, Jozef

Subject:	Graph Theory
	» Topological Graph Theory
	» » Crossing numbers

Keywords:	crossing number
	crossing sequence

Recomm. for undergrads: no

Posted	by:	Robert Samal
	on:	July 30th, 2008

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.

This actually are two conjectures, one for the orientable case and another for nonorientable one. For sequences $(a_0,a_1,0)$ the nonorientable case was resolved in [ABS] and the orientable one in [DMS].

The conclusion also holds (for the orientable case) whenever the sequence $(a_i)$ is convex [S], that is whenever $a_i - a_{i-1}$ is nonincreasing. It might seem that this condition is also necessary: For the most extreme sequence $(N,N-1,0)$ (suggested by Salazar) one needs to construct a graph for which adding one handle saves just one crossing, while adding another saves many -- but then why not add the second handle first? Somewhat surprisingly, graphs with this counterintuitive property exist, at least for sequences $(a_0,a_1,0)$ .