EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Simple Realizability of Abstract Topological Graphs

Giordano Da Lozzo, Walter Didimo, Fabrizio Montecchiani, Miriam Münch, Maurizio Patrignani, Ignaz Rutter

Algorithmica · 2027-02 · 89 (1)

DOI: 10.1007/s00453-026-01413-4 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Algorithmica, online erschienen am 02.11.2026. Verfasst von Giordano Da Lozzo und 5 weiteren Autor:innen. Die Arbeit nennt 30 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Ministero dell’Università e della Ricerca, Deutsche Forschungsgemeinschaft.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

An abstract topological graph ( AT-graph ) is a pair $$A=(G,\mathcal {X})$$ A = ( G , X ) , where $$G=(V,E)$$ G = ( V , E ) is a graph and $$\mathcal {X} \subseteq \left( {\begin{array}{c}E\\ 2\end{array}}\right) $$ X ⊆ E 2 is a set of pairs of edges of G . A realization of A is a drawing $$\Gamma _A$$ Γ A of G in the plane such that any two edges $$e_1,e_2$$ e 1 , e 2 of G cross in $$\Gamma _A$$ Γ A if and only if $$(e_1,e_2) \in \mathcal {X} $$ ( e 1 , e 2 ) ∈ X ; $$\Gamma _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 $$\mathrm {\lambda }(A)$$ λ ( A ) of the largest connected component of the crossing graph of any realization of A , i.e., the graph $$\mathcal{C}(A) = (E, \mathcal {X})$$ 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 -complete when $$\mathrm {\lambda }(A) \ge 6$$ λ ( A ) ≥ 6 . On the positive side, we give an optimal linear-time algorithm that solves SATR when $$\mathrm {\lambda }(A) \le 3$$ λ ( 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.

Förderung

  • Ministero dell’Università e della Ricerca
  • Deutsche Forschungsgemeinschaft

Zitieren

APA

Lozzo, G. D., Didimo, W., Montecchiani, F., Münch, M., Patrignani, M., & Rutter, I. (2027). Simple Realizability of Abstract Topological Graphs. Algorithmica, 89(1). https://doi.org/10.1007/s00453-026-01413-4

Vancouver

Lozzo GD, Didimo W, Montecchiani F, Münch M, Patrignani M, Rutter I. Simple Realizability of Abstract Topological Graphs. Algorithmica. 2027;89(1). doi:10.1007/s00453-026-01413-4

BibTeX
@article{Lozzo2027,
  author = {Lozzo, Giordano Da and Didimo, Walter and Montecchiani, Fabrizio and Münch, Miriam and Patrignani, Maurizio and Rutter, Ignaz},
  title = {Simple Realizability of Abstract Topological Graphs},
  journal = {Algorithmica},
  year = {2027},
  volume = {89},
  number = {1},
  doi = {10.1007/s00453-026-01413-4}
}
Kostenlos starten →