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

13. Far-away crossing pairs

    1. Far-away crossing pairs

          Let $f(n)$ be the maximum number of edges in a graph $G$ that can be drawn in the plane such that the distance of every pair of crossing edges is at least $100$. Here, the distance between a pair of edges is the length of the shortest path with them as two ending edges respectively.

      Add remark

      Problem 13.1.

      [Gabor Tardos] Determine $f(n)$ asymptotically.
          Note: Under the condition that the edges are drawn as straight-line segments (i.e. geometric graphs), we have $\Omega(n \cdot \log^{(50)}n) \leq f(n) \leq O(\frac{n\log n}{\log \log n})$. Here $\log^{(50)}n$ means taking $\log$ for $50$ times, i.e. $\log^{(3)} n = \log \log \log n$.

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