Journal of Graph Algorithms and Applications
|Home||Issues||Aims and Scope||Instructions for Authors|
Special Issue on Selected Papers from the Eleventh International Symposium on Graph Drawing, GD 2003
Experiments with the Fixed-Parameter Approach for Two-Layer Planarization
Vol. 9, no. 1, pp. 149-163, 2005. Regular paper.
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.
Submitted: February 2004.
Revised: July 2005.
Communicated by Giuseppe Liotta