Simple Realizability of Abstract Topological Graphs

An abstract topological graph ( AT-graph ) is a pair A=(G,X) A = ( G , X ) , where $$G=(V,E)$$ G = ( V , E ) is a graph and X ⊆ ( arraycE\\ 2array) X ⊆ E 2 is a set of pairs of edges of G . A realization of A is a drawing Γ A Γ A of G in the plane such that any two edges e₁,e₂ e 1 , e 2 of G cross in Γ A Γ A if and only if (e₁,e₂) ∈ X ( e 1 , e 2 ) ∈ X ; Γ A Γ 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 classic result that both ATR and SATR are -complete [18, 21]. In this paper, we study the SATR problem from a new structural perspective. More precisely, we consider the size λ (A) λ ( A ) of the largest connected component of the crossing graph of any realization of A , i.e., the graph C(A) = (E, X) C ( A ) = ( E , X )