Heuristics for Exact 1-Planarity Testing

Abstract

Since many real-world graphs are nonplanar, the study of graphs that10
allow few crossings per edge has been an active subfield of graph theory in recent years.11
One of the most natural generalizations of planar graphs are the so-called 1-planar12
graphs that admit a drawing with at most one crossing per edge. Unfortunately, testing13
whether a graph is 1-planar is known to be NP-complete even for very restricted graph14
classes. On the positive side, Binucci, Didimo and Montecchiani [7] presented the first15
practical algorithm for testing 1-planarity based on an easy-to-implement backtracking16
strategy. We build on this idea and systematically explore the design choices of such17
algorithms and propose several new ingredients, such as different branching strategies18
and multiple filter criteria that allow us to reject certain branches in the search tree19
early on. We conduct an extensive experimental evaluation that evaluates the efficiency20
and effectiveness of these ingredients. Given a time limit of three hours per instance,21
our best configuration is able to solve more than 98% of the non-planar instances from22
the well-known North and Rome graphs with up to 50 vertices. Notably, the median23
running time for solved instances is well below 1 second.