2026-07-25T00:41:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24990 2026-02-09T07:52:32Z ddc:004 open_access

Heuristics for Exact 1-Planarity Testing Fink, Simon D. Münch, Miriam Pfretzschner, Matthias Rutter, Ignaz 1-Planarity Experiments Backtracking Since many real-world graphs are nonplanar, the study of graphs that allow few crossings per edge has been an active subfield of graph theory in recent years. One of the most natural generalizations of planar graphs are the so-called 1-planar graphs that admit a drawing with at most one crossing per edge. Unfortunately, testing whether a graph is 1-planar is known to be NP-complete even for very restricted graph classes. On the positive side, Binucci, Didimo and Montecchiani [Binucci et al., 2023] presented the first practical algorithm for testing 1-planarity based on an easy-to-implement backtracking strategy. We build on this idea and systematically explore the design choices of such algorithms and propose several new ingredients, such as different branching strategies and multiple filter criteria that allow us to reject certain branches in the search tree early on. We conduct an extensive experimental evaluation that evaluates the efficiency and effectiveness of these ingredients. Given a time limit of three hours per instance, our best configuration is able to solve more than 95% of the non-planar instances from the well-known North and Rome graphs with up to 50 vertices. Notably, the median running time for solved instances is well below 4 seconds. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Simon D. Fink and Miriam Münch and Matthias Pfretzschner and Ignaz Rutter 2025 Is Part Of LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.GD.2025.4 urn:nbn:de:0030-drops-249909 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.4 eng https://creativecommons.org/licenses/by/4.0/legalcode