English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We present a deterministic $n^{2+o(1)}$-time algorithm that approximates thecrossing number of any graph $G$ of order $n$ up to an additive error of$o(n^4)$. We also provide a randomized polynomial-time algorithm thatconstructs a drawing of $G$ with $\text{cr}(G)+o(n^4)$ crossings. These resultsare made interesting by the well known fact that every dense $n$-vertex graphhas crossing number $\Theta(n^4)$. Our work builds on a technique developed byFox, Pach and S\'uk, who obtained very similar results for the rectilinearcrossing number.  The results by the aforementioned authors and in this paper imply that the(normalized) crossing and rectilinear crossing numbers are estimableparameters. Motivated by this, we introduce two graphon parameters, thecrossing density and the rectilinear crossing density, and then we prove that,in a precise sense, these are the correct continuous analogs of the crossingand rectilinear crossing numbers of graphs.

An algorithm for estimating the crossing number of dense graphs, and continuous analogs of the crossing and rectilinear crossing numbers