Experiments with the Fixed-Parameter Approach for Two-Layer Planarization

Abstract

We present computational results of an implementation based on the fixed parameter tractability (FPT) approach for biplanarizing graphs. These results show that the implementation can efficiently find minimum biplanarizing sets containing up to about 18 edges, thus making it comparable to previous integer linear programming approaches. We show how our implementation slightly improves the theoretical running time to O(6^\bpr(G)+|G|) for any input graph G. Finally, we explain how our experimental work predicts how performance on sparse graphs may be improved.