2026-07-24T10:14:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22150 2024-12-04T06:53:44Z ddc:004 open_access

Simple Realizability of Abstract Topological Graphs Da Lozzo, Giordano Didimo, Walter Montecchiani, Fabrizio Münch, Miriam Patrignani, Maurizio Rutter, Ignaz Abstract Topological Graphs SPQR-Trees Synchronized PQ-Trees 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Giordano Da Lozzo and Walter Didimo and Fabrizio Montecchiani and Miriam Münch and Maurizio Patrignani and Ignaz Rutter 2024 Is Part Of LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2024.23 urn:nbn:de:0030-drops-221501 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.23 eng https://creativecommons.org/licenses/by/4.0/legalcode