Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
|
DOI: 10.7155/jgaa.00103 Experiments with the Fixed-Parameter Approach for Two-Layer Planarization Matthew Suderman and Sue Whitesides 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.
|
Revised: July 2005. Submitted: February 2004. Communicated by Giuseppe Liotta |
| Journal of Graph Algorithms and Applications |