A slightly better bound on the crossing number in terms of the pair-crossing number

arXiv2105.14319MaRDI QIDQ6368879

János Karl, Géza Tóth

Publication date: 29 May 2021

Abstract: The crossing number of a graph $G$, $mboxcr(G)$, is the minimum number of crossings, the pair-crossing number, $mboxpcr(G)$, is the minimum number of pairs of crossing edges over all drawings of $G$. In this note we show that $mboxcr(G)=O(mboxpcr(G{)}^{3/2}logmboxpcr(G))$, which is an improvement of the result of Matouv{s}ek, by a log factor.

This page was built for publication: A slightly better bound on the crossing number in terms of the pair-crossing number