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, Perugia, Italy , pp. 345-356 (Official URL: http://dx.doi.org/10.1007/978-3-540-24595-7_32).

Full text not available from this repository.

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 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
ID Code:464

Repository Staff Only: item control page

References

Battista, G.D., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall (1999).

Downey, R.G., Fellows, M.R.: Parametrized Complexity. Springer-Verlag (1999).

Dujmovic, V., Fellows, M.R., Hallett, M.T., Kitching, M., Liotta, G., McCartin, C., Nishimura, N., Ragde, P., Rosamond, F.A., Suderman, M., Whitesides, S., Wood, D.R.: A fixed-parameter approach to two-layer planarization. In Mutzel, P., Jünger, M., Leipert, S., eds.: Graph Drawing, 9th International Symposium (GD 2001). Volume 2265 of Lecture Notes in Computer Science., Springer-Verlag (2001) 1-15.

Dujmovic, V., Fellows, M.R., Hallett, M.T., Kitching, M., Liotta, G., McCartin, C., Nishimura, N., Ragde, P., Rosamond, F.A., Suderman, M., Whitesides, S., Wood, D.R.: A fixed-parameter approach to two-layer planarization, manuscript (2003)

Eades, P., McKay, B., Wormald, N.: On an edge crossing problem. In: Proceedings of the 9th Australian Computer Science Conference, Australian National University (1986) 327-334.

Garey, M.R., Johnson, D.S.: Crosssing number is NP-complete. SIAM Journal of Algebraic Discrete Methods 4 (1983) 312-316.

Harary, F., Schwenk, A.: A new crossing number for bipartite graphs. Utilitas Mathematica 1 (1972) 203-209.

Jünger, M., Mutzel, P.: 2-layer straightline crossing minimization: performance of exact and heuristic algorithms. Journal of Graph Algorithms and Applications 1 (1997) 1-25.

Jünger, M., Thienel, S.: The ABACUS-system for branch and cut and price algorithms in integer programming and combinatorial optimization. In: Software-Practice and Experience. Volume 30. (2000) 1324-1352.

Knuth, D.: The Stanford Graph Base: A Platform for Combinatorial Computing ACM Press, Addison-Wesley Publishing Company (1993).

Lengauer, T.: Combinatorial Algorithms for Integrated Circuit Layout. Wiley (1990).

Mutzel, P.: An alternative method to crossing minimization on hierarchical graphs. In North, S.C., ed.: Graph Drawing, Symposium on Graph Drawing (GD '96). Volume 1190 of Lecture Notes in Computer Science., Springer-Verlag (1996) 318-333.

Mutzel, P.: An alternative method to crossing minimization on hierarchical graphs. SIAM Journal of Optimization 11 (2001) 1065-1080.

Sugiyama, K., Tagawa, S., Toda, M.: Methods for visual understanding of hierarchical system structures. IEEE Transactions on Systems, Man, and Cybernetics 11 (1981) 109-125.

Tomii, N., Kambayashi, Y., Yajima, S.: On planarization algorithms of 2-level graphs. Papers of tech. group on elect. comp., IECEJ EC77-38 (1977) 1-12.

Warfield, J.N.: Crossing theory and hierarchy mapping. IEEE Transactions on Systems, Man and Cybernetics 7 (1977) 502-523.

Waterman, M.S., Griggs, J.R.: Interval graphs and maps of DNA. Bulletin of Mathematical Biology 48 (1986) 189-195.