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

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 lie along two parallel lines ℓ b and ℓ r , respectively, each edge in E is drawn in the unbounded strip of the plane delimited by ℓ b and ℓ r , and no three edges in E pairwise cross.

We prove that the 2-Level Quasi-Planarity problem is NP-complete. This answers an open question of Dujmović, Pór, and Wood. Furthermore, we show that the problem becomes linear-time solvable if the ordering of the vertices in V b along ℓ b is prescribed. Our contributions provide the first results on the computational complexity of recognizing quasi-planar graphs, which is a long-standing open question.

Our linear-time algorithm exploits several ingredients, including a combinatorial characterization of the positive instances of the problem in terms 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 planar embedding. Our algorithm builds upon a classification of the types of embeddings with respect to the structure of the portion of the caterpillar they contain and performs a computation of the realizable embedding types based on a succinct description of their features by means of constant-size gadgets.