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

16. Plane paths in simple topological graphs

    1. Plane paths in simple topological graphs

          A drawing (i.e. topological graph) is said to be simple if any two edges intersect at most once, either at a common ending point or a proper crossing point. Let $f(n)$ be the maximum length of a non-crossing (i.e. plane) path in any complete simple topological graph on $n$ vertices. It’s known that $f(n) \geq \Omega(\log n /\log \log n)$.

      Add remark

      Problem 16.1.

      [Andrew Suk] Is there a constant $c > 0$ such that $f(n) \geq \Omega(n^c)$?
          Note: 1. It is not disproved that every complete simple topological graph (at least three vertices) contains a non-crossing Hamiltonian cycle. 2. One can find $\Omega(\sqrt{n})$ many disjoint edges. 3. Maybe these problems make sense for dense (not necessarily complete) graphs.

      Reference: O. Aichholzer, A. Garcia, J. Tejel, B. Vogtenhuber, A. Weinberger. Twisted Ways to Find Plane Structures in Simple Drawings of Complete Graphs. Discrete & Computational Geometry 71 (2024): 40–66.

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