Home | Issues | About JGAA | Instructions for Authors |
Special Issue on Selected Papers from the Eleventh International Symposium on Graph Drawing, GD 2003
DOI: 10.7155/jgaa.00103
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.
|
Journal Supporters
|