OOPS: Optimized One-Planarity Solver via SAT
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).
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}
}
EUVIMED