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

Given a bipartite graph $G=(V_b,V_r,E)$, the $2$-Level Quasi-Planarityproblem asks for the existence of a drawing of $G$ in the plane such that thevertices in $V_b$ and in $V_r$ lie along two parallel lines $\ell_b$ and$\ell_r$, respectively, each edge in $E$ is drawn in the unbounded strip of theplane delimited by $\ell_b$ and $\ell_r$, and no three edges in $E$ pairwisecross.  We prove that the $2$-Level Quasi-Planarity problem is NP-complete. Thisanswers an open question of Dujmovi\'c, P\'{o}r, and Wood. Furthermore, we showthat the problem becomes linear-time solvable if the ordering of the verticesin $V_b$ along $\ell_b$ is prescribed. Our contributions provide the firstresults on the computational complexity of recognizing quasi-planar graphs,which is a long-standing open question.  Our linear-time algorithm exploits several ingredients, including acombinatorial characterization of the positive instances of the problem interms of the existence of a planar embedding with a caterpillar-like structure,and an SPQR-tree-based algorithm for testing the existence of such a planarembedding. Our algorithm builds upon a classification of the types ofembeddings with respect to the structure of the portion of the caterpillar theycontain and performs a computation of the realizable embedding types based on asuccinct description of their features by means of constant-size gadgets.

2-Level Quasi-Planarity or How Caterpillars Climb (SPQR-)Trees