Simple Realizability of Abstract Topological Graphs

An abstract topological graph (AT-graph) is a pair A = (G, X), where G = (V,E) is a graph and X ⊆ binom(E,2) is a set of pairs of edges of G. A realization of A is a drawing Γ_A of G in the plane such that any two edges e₁,e₂ of G cross in Γ_A if and only if (e₁,e₂) ∈ X; Γ_A is simple if any two edges intersect at most once (either at a common endpoint or at a proper crossing). The AT-graph Realizability (ATR) problem asks whether an input AT-graph admits a realization. The version of this problem that requires a simple realization is called Simple AT-graph Realizability (SATR). It is a classical result that both ATR and SATR are NP-complete [Kratochvíl, 1991; Kratochvíl and Matoušek, 1989]. In this paper, we study the SATR problem from a new structural perspective. More precisely, we consider the size λ(A) of the largest connected component of the crossing graph of any realization of A, i.e., the graph C(A) = (E, X). This parameter represents a natural way to measure the level of interplay among edge crossings. First, we prove that SATR is NP-complete when λ(A) ≥ 6. On the positive side, we give an optimal linear-time algorithm that solves SATR when λ(A) ≤ 3 and returns a simple realization if one exists. Our algorithm is based on several ingredients, in particular the reduction to a new embedding problem subject to constraints that require certain pairs of edges to alternate (in the rotation system), and a sequence of transformations that exploit the interplay between alternation constraints and the SPQR-tree and PQ-tree data structures to eventually arrive at a simpler embedding problem that can be solved with standard techniques.