Skewness, crossing number and Euler's bound for graphs on surfaces

Abstract

For every connected graph $G$ and surface $S$, we consider the well-known string of inequalities $\hat{I}{´}_S(G)\le \hat{I}{¼}_S(G)\le \hat{I}{½}_S(G)$, where $\hat{I}¼$ and $\hat{I}½$ denote skewness and crossing number and $\hat{I}´$ is the Euler-formula lower bound. Recent developments are surveyed; new results are given for the ``folded'' cube including its genus.

16 pages, 57 references