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

12. Subgraphs of quasi-planar graphs

    1. Quasi-planar graphs

          A graph is said to be $k$-quasi-planar if it can be drawn in the plane with no $k$ pairwise crossing edges. It is a classical problem whether quasi-planar graphs have a linear number of edges.

      Add remark

      Problem 12.1.

      [Radoslav Fulek] Is it true that for every fixed $k$ the genus $g(G)$ (Euler or orientable) of all $k$-quasi-planar graphs $G$ is in $O(n)$?
          Reference: B. Mohar, C. Thomassen. Graphs on Surfaces. Johns Hopkins University Press, 2001.

      J. Pach, F. Shahrokhi, M. Szegedy. Applications of the crossing number. Algorithmica 16 (1996): 111–117.

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