| Register
\(\newcommand{\Cat}{{\rm Cat}} \) \(\newcommand{\A}{\mathcal A} \) \(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)

5. Crossing number on surfaces

    1. Crossing number on surfaces

          Let $\text{cr}_g(G)$ be the minimum number of crossings in a drawing of $G$ on a surface of genus $g$. It is known that $\Omega\left(\frac{n^4}{g} \right) \leq \text{cr}_g(K_n) \leq O\left(\frac{(\log g)^2n^4}{g} \right)$, under the condition that $g$ is not too large such that the problem becomes trivial.

      Add remark

      Problem 5.1.

      [Laszlo Szekeley] Study $\text{cr}_g(K_n)$ and obtain better bounds.
          Reference: F. Shahrokhi, L. A. Szekely, O. Sykora, I. Vrto. Drawings of Graphs on Surfaces with Few Crossings. Algorithmica 16 (1996): 118–131.

          Cite this as: AimPL: Albertson conjecture and related problems, available at http://aimpl.org/albertson.