Fixed Parameter Tractability of Crossing Minimization of Almost-Trees

Bannister, Michael J. and Eppstein, David and Simons, Joseph A. (2013) Fixed Parameter Tractability of Crossing Minimization of Almost-Trees. In: 21st International Symposium, GD 2013, September 23-25, 2013, Bordeaux, France , pp. 340-351 (Official URL:

Full text not available from this repository.


We investigate exact crossing minimization for graphs that differ from trees by a small number of additional edges, for several variants of the crossing minimization problem. In particular, we provide fixed parameter tractable algorithms for the 1-page book crossing number, the 2-page book crossing number, and the minimum number of crossed edges in 1-page and 2-page book drawings.

Item Type:Conference Paper
Classifications:G Algorithms and Complexity > G.420 Crossings
G Algorithms and Complexity > G.999 Others
ID Code:1387

Repository Staff Only: item control page


ach, J., Tóth, G.: Which crossing number is it anyway? J. Combin. Theory Ser. B 80(2), 225–246 (2000)

Gurevich, Y., Stockmeyer, L., Vishkin, U.: Solving NP-hard problems on graphs that are almost trees and an application to facility location problems. J. ACM 31(3), 459–473 (1984)

Fernández-Baca, D.: Allocating modules to processors in a distributed system. IEEE Transactions on Software Engineering 15(11), 1427–1436 (1989)

Kloks, T., Bodlaender, H., Müller, H., Kratsch, D.: Computing treewidth and minimum fill-in: All you need are the minimal separators. In: Lengauer, T. (ed.) ESA 1993. LNCS, vol. 726, pp. 260–271. Springer, Heidelberg (1993)

Akutsu, T., Hayashida, M., Ching, W.K., Ng, M.K.: Control of Boolean networks: Hardness results and algorithms for tree structured networks. J. Theor. Bio. 244(4), 670–679 (2007)

Fiala, J., Kloks, T., Kratochvíl, J.: Fixed-parameter complexity of λ-labelings. Discrete Appl. Math. 113(1), 59–72 (2001)

Coppersmith, D., Vishkin, U.: Solving NP-hard problems in ‘almost trees’: Vertex cover. Discrete Appl. Math. 10(1), 27–45 (1985)

Bodlaender, H.: Dynamic algorithms for graphs with treewidth 2. In: van Leeuwen, J. (ed.) WG 1993. LNCS, vol. 790, pp. 112–124. Springer, Heidelberg (1994)

Fürer, M.: Counting perfect matchings in graphs of degree 3. In: Kranakis, E., Krizanc, D., Luccio, F. (eds.) FUN 2012. LNCS, vol. 7288, pp. 189–197. Springer, Heidelberg (2012)

Grohe, M.: Computing crossing numbers in quadratic time. In: ACM Symp. Theory of Computing (STOC 2001), pp. 231–236 (2001)

Kawarabayashi, K.I., Reed, B.: Computing crossing number in linear time. In: ACM Symp. Theory of Computing (STOC 2007), pp. 382–390 (2007)

Pelsmajer, M.J., Schaefer, M., Štefankovič, D.: Crossing number of graphs with rotation systems. In: Hong, S.-H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol. 4875, pp. 3–12. Springer, Heidelberg (2008)

Chung, F.R.K., Leighton, F.T., Rosenberg, A.L.: Embedding graphs in books: A layout problem with applications to VLSI design. SIAM J. Alg. Disc. Meth. 8(1), 33–58 (1987)

Potterat, J.J., Phillips-Plummer, L., Muth, S.Q., Rothenberg, R.B., Woodhouse, D.E., Maldonado-Long, T.S., Zimmerman, H.P., Muth, J.B.: Risk network structure in the early epidemic phase of HIV transmission in Colorado Springs. Sexually Transmitted Infections 78(suppl. 1), i159–i163 (2002)

De, P., Singh, A.E., Wong, T., Yacoub, W., Jolly, A.M.: Sexual network analysis of a gonorrhoea outbreak. Sexually Transmitted Infections 80(4), 280–285 (2004)

Potterat, J.J., Muth, S.Q., Rothenberg, R.B., Zimmerman-Rogers, H., Green, D.L., Taylor, J.E., Bonney, M.S., White, H.A.: Sexual network structure as an indicator of epidemic phase. Sexually Transmitted Infections 78(suppl. 1), i152–i158 (2002)

Lombardi, M., Hobbs, R.: Mark Lombardi: Global Networks. Independent Curators (2003)

Butts, C.T., Acton, R.M., Marcum, C.S.: Interorganizational collaboratio in the Hurricane Katrina response. J. Social Structure 13(1) (2012)

Seidman, S.B.: Network structure and minimum degree. Social Networks 5(3), 269–287 (1983)

de Nooy, W., Mrvar, A., Batagelj, V.: Exploratory Social Network Analysis with Pajek. Cambridge University Press (2012)

Watts, D., Strogatz, S.: Collective dynamics of ‘small-world’ networks. Nature 393, 440–442 (1998)

Bannister, M.J., Cabello, S., Eppstein, D.: Parameterized complexity of 1-planarity. In: Dehne, F., Solis-Oba, R., Sack, J.-R. (eds.) WADS 2013. LNCS, vol. 8037, pp. 97–108. Springer, Heidelberg (2013)

Masuda, S., Kashiwabara, T., Nakajima, K., Fujisawa, T.: On the NP-completeness of a computer network layout problem. In: 20th IEEE Symp. Circuits and Systems, pp. 292–295 (1987)

Baur, M., Brandes, U.: Crossing reduction in circular layouts. In: Hromkovič, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol. 3353, pp. 332–343. Springer, Heidelberg (2004)

Sedgewick, R.: Permutation generation methods. ACM Comput. Surv. 9(2), 137–164 (1977)

Masuda, S., Nakajima, K., Kashiwabara, T., Fujisawa, T.: Crossing minimization in linear embeddings of graphs. IEEE Trans. Computers 39(1), 124–127 (1990)

Williams, R.: A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci. 348(2-3), 357–365 (2005)

Williams, V.V.: Multiplying matrices faster than Coppersmith–Winograd. In: ACM Symp. Theory of Computing (STOC 2012), pp. 887–898 (2012)

Alon, N., Galil, Z., Margalit, O.: On the exponent of the all pairs shortest path problem. J. Comput. Sys. Sci. 54(2), 255–262 (1997)

Yuval, G.: An algorithm for finding all shortest paths using N 2.81 infinite-precision multiplications. Inf. Proc. Lett. 4(6), 155–156 (1976)