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/

Zendy Plus

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

Zendy Tools

Zendy Open

A graph is near-planar if it can be obtained from a planar graph by adding anedge. We show the surprising fact that it is NP-hard to compute the crossingnumber of near-planar graphs. A graph is 1-planar if it has a drawing whereevery edge is crossed by at most one other edge. We show that it is NP-hard todecide whether a given near-planar graph is 1-planar. The main idea in bothreductions is to consider the problem of simultaneously drawing two planargraphs inside a disk, with some of its vertices fixed at the boundary of thedisk. This leads to the concept of anchored embedding, which is of independentinterest. As an interesting consequence we obtain a new, geometric proof ofNP-completeness of the crossing number problem, even when restricted to cubicgraphs. This resolves a question of Hlin\v{e}n\'y.

Adding one edge to planar graphs makes crossing number and 1-planarity hard