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

Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista +2

Given a bipartite graph $G=(V_b,V_r,E)$, the $2$-Level Quasi-Planarity problem asks for the existence of a drawing of $G$ in the plane such that the vertices in $V_b$ and in $V_r$…