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

Suderman, Matthew and Whitesides, Sue (2004) Experiments with the Fixed-Parameter Approach for Two-Layer Planarization. In: Graph Drawing 11th International Symposium, GD 2003, September 21-24, 2003 , pp. 345-356(Official URL: http://dx.doi.org/10.1007/978-3-540-24595-7_32).

Full text not available from this repository.


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 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|). Finally, we explain how our experimental work predicts how performance on sparse graphs may be improved.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-24595-7_32
Classifications: G Algorithms and Complexity > G.420 Crossings
P Styles > P.480 Layered
URI: http://gdea.informatik.uni-koeln.de/id/eprint/464

Actions (login required)

View Item View Item