{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,25]],"date-time":"2026-07-25T15:01:35Z","timestamp":1784991695277,"version":"3.55.0"},"reference-count":0,"publisher":"Journal of Graph Algorithms and Applications","issue":"2","license":[{"start":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T00:00:00Z","timestamp":1784246400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["JGAA"],"abstract":"<jats:p>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\u00efve 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.<\/jats:p>","DOI":"10.7155\/jgaa.v30i2.3114","type":"journal-article","created":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T14:14:14Z","timestamp":1784297654000},"page":"175-197","source":"Crossref","is-referenced-by-count":0,"title":["OOPS: Optimized One-Planarity Solver via SAT"],"prefix":"10.7155","volume":"30","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4089-673X","authenticated-orcid":false,"given":"Sergey","family":"Pupyrev","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"4175","published-online":{"date-parts":[[2026,7,17]]},"container-title":["Journal of Graph Algorithms and Applications"],"original-title":[],"link":[{"URL":"https:\/\/jgaa.info\/index.php\/jgaa\/article\/download\/3114\/3041","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/jgaa.info\/index.php\/jgaa\/article\/download\/3114\/3041","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,25]],"date-time":"2026-07-25T14:15:34Z","timestamp":1784988934000},"score":1,"resource":{"primary":{"URL":"https:\/\/jgaa.info\/index.php\/jgaa\/article\/view\/3114"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,17]]},"references-count":0,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2026,4,28]]}},"URL":"https:\/\/doi.org\/10.7155\/jgaa.v30i2.3114","relation":{},"ISSN":["1526-1719"],"issn-type":[{"value":"1526-1719","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,7,17]]}}}