EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

OOPS: Optimized One-Planarity Solver via SAT

Sergey Pupyrev

Journal of Graph Algorithms and Applications · 17.07.2026 · 30 (2) · 175-197

DOI: 10.7155/jgaa.v30i2.3114 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Graph Algorithms and Applications, online erschienen am 17.07.2026. Verfasst von Sergey Pupyrev. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We present OOPS (Optimized One-Planarity Solver), a practical heuristicfor recognizing 1-planar graphs and several important subclasses. A graphis 1-planar if it can be drawn in the plane such that each edge is crossed at mostonce---a natural generalization of planar graphs that has received increasingattention in graph drawing and beyond-planar graph theory. Although testing planarity can be done in linear time,recognizing 1-planar graphs is NP-complete, making effective practical algorithms especially valuable.The core idea of our approach is to reduce the recognition of 1-planarity to a propositional satisfiability (SAT) instance,enabling the use of modern SAT solvers to efficiently explore the search space. Despite the inherent complexityof the problem, our method is substantially faster in practice than naïve or brute-force algorithms.In addition to demonstrating the empirical performance of our solver on synthetic and real-worldinstances, we show how OOPS can be used as a discovery tool in theoretical graph theory. Specifically,we employ OOPS to investigate two research problems concerning 1-planarity of specific graph families.Our implementation of the algorithm is publicly available to support further exploration in the field.

Zitieren

APA

Pupyrev, S. (2026). OOPS: Optimized One-Planarity Solver via SAT. Journal of Graph Algorithms and Applications, 30(2), 175-197. https://doi.org/10.7155/jgaa.v30i2.3114

Vancouver

Pupyrev S. OOPS: Optimized One-Planarity Solver via SAT. Journal of Graph Algorithms and Applications. 2026;30(2):175-197. doi:10.7155/jgaa.v30i2.3114

BibTeX
@article{Pupyrev2026,
  author = {Pupyrev, Sergey},
  title = {OOPS: Optimized One-Planarity Solver via SAT},
  journal = {Journal of Graph Algorithms and Applications},
  year = {2026},
  volume = {30},
  number = {2},
  pages = {175--197},
  doi = {10.7155/jgaa.v30i2.3114}
}
Kostenlos starten →