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

6. Crossing number within a circle

    1. Crossing number within a circle

          Let $\text{cr}_{\circ}(G)$ be the minimum number of crossings of a drawing of $G$ under the condition that the vertices of $G$ in placed on the unit circle and the edges of $G$ are drawn within the unit disc.

      Add remark

      Problem 6.1.

      [Jacob Fox] Study $\text{cr}_\circ(G)$.
          Note: Several participants pointed out that $\text{cr}_\circ(G)$ is known as the convex crossing number. Shahrokhi et al. studied this concept and proved e.g., that this kind of crossing number of the $\sqrt{n}\times \sqrt{n}$ grid is $n \log n$.

      Reference: F. Shahrokhi, O. Sykora, L.A. Szekely, I. Vrto. The gap between the crossing number and the convex crossing number. Towards a Theory of Geometric Graphs, Eds. J. Pach, Contemporary Mathematics 342 2004, 249–258.

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