Practical Experience with Hanani-Tutte for Testing c-Planarity

摘要

We propose an algorithm for c-planarity testing which is correct and efficient, but not, in general, complete, i.e., there are input instances on which the algorithm declines to give an answer. At the core of this algorithm is an algebraic criterion based on work by the third author [20] with the following properties: (1) The criterion is a necessary condition for c-planarity, (2) for special graph classes, including c-connected graphs, the condition is also sufficient, and (3) the criterion can be tested efficiently in polynomial time. The algebraic criterion is not sufficient in general; however, we can extend it to a (still efficient) algorithm that verifies the answer of the criterion by building a c-planar embedding of the input graph. Our practical experiments show that this algorithm works well in practice. This is the first time that all instances from state-of-the-art benchmark sets for testing c-planarity are solved correctly. The algorithm is conceptually very simple and easy to implement.