Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth

Bannister, Michael J. and Eppstein, David (2014) Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014, Würzburg, Germany , pp. 210-221 (Official URL:

Full text not available from this repository.


We investigate crossing minimization for 1-page and 2-page book drawings. We show that computing the 1-page crossing number is fixed-parameter tractable with respect to the number of crossings, that testing 2-page planarity is fixed-parameter tractable with respect to treewidth, and that computing the 2-page crossing number is fixed-parameter tractable with respect to the sum of the number of crossings and the treewidth of the input graph. We prove these results via Courcelle’s theorem on the fixed-parameter tractability of properties expressible in monadic second order logic for graphs of bounded treewidth.

Item Type:Conference Paper
Additional Information:10.1007/978-3-662-45803-7_18
Classifications:G Algorithms and Complexity > G.420 Crossings
G Algorithms and Complexity > G.490 Embeddings
M Methods > M.999 Others
P Styles > P.540 Planar
P Styles > P.999 Others
Z Theory > Z.750 Topology
ID Code:1434

Repository Staff Only: item control page


Arnborg, S., Corneil, D., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM J. Alg. Disc. Meth. 8(2), 277–284 (1987), doi:10.1137/0608024

Auslander, L., Parter, S.V.: On imbedding graphs in the sphere. Journal of Mathematics and Mechanics 10(3), 517–523 (1961)

Bannister, M.J., Eppstein, D., Simons, J.A.: Fixed parameter tractability of crossing minimization of almost-trees. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 340–351. Springer, Heidelberg (2013), doi:10.1007/978-3-319-03841-4_30

Bernhart, F., Kainen, P.C.: The book thickness of a graph. Journal of Combinatorial Theory, Series B 27(3), 320–331 (1979), doi:10.1016/0095-8956(79)90021-2

Bodlaender, H.L.: A linear time algorithm for finding tree-decompositions of small treewidth. In: Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing, STOC 1993, pp. 226–234. ACM (1993), doi:10.1145/167088.167161

Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theoretical Computer Science 209(1-2), 1–45 (1998), doi:10.1016/S0304-3975(97)00228-4

Chartrand, G., Harary, F.: Planar permutation graphs. Annales de l’institut Henri Poincaré (B) Probabilités et Statistiques 3(4), 433–438 (1967),

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), doi:10.1137/0608002

Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Information and Computation 85(1), 12–75 (1990), doi:10.1016/0890-5401(90)90043-H

Courcelle, B., Engelfriet, J.: Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach. Cambridge University Press (2012)

Dujmović, V., Fellows, M.R., Kitching, M., Liotta, G., McCartin, C., Nishimura, N., Ragde, P., Rosamond, F., Whitesides, S., Wood, D.R.: On the parameterized complexity of layered graph drawing. Algorithmica 52(2), 267–292 (2008), doi:10.1007/s00453-007-9151-1

Dujmović, V., Wood, D.R.: Graph treewidth and geometric thickness parameters. Discrete Comput. Geom. 37(4), 641–670 (2007), doi:10.1007/s00454-007-1318-7

Ebbinghaus, H.-D., Flum, J., Thomas, W.: Mathematical logic, 2nd edn. Undergraduate Texts in Mathematics. Springer (1994), doi:10.1007/978-1-4757-2355-7; Translated from the German by Margit Meßmer

Goldstein, A.J.: An efficient and constructive algorithm for testing whether a graph can be embedded in a plane. In: Graph and Combinatorics Conference (1963)

Grohe, M.: Computing crossing numbers in quadratic time. Journal of Computer and System Sciences 68(2), 285–302 (2004), doi:10.1016/j.jcss.2003.07.008

Kainen, P.C.: Some recent results in topological graph theory. In: Graphs and Combinatorics. Lecture Notes in Mathematics, vol. 406, pp. 76–108. Springer (1974), doi:10.1007/BFb0066436

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

Mitchell, S.L.: Linear algorithms to recognize outerplanar and maximal outerplanar graphs. Information Processing Letters 9(5), 229–232 (1979), doi:10.1016/0020-0190(79)90075-9

Ollmann, L.T.: On the book thicknesses of various graphs. In: Proc. 4th Southeastern Conference on Combinatorics, Graph Theory and Computing, vol. 8, p. 459 (1973)

Pelsmajer, M.J., Schaefer, M., Štefankovič, D.: Crossing numbers and parameterized complexity. In: Hong, S.-H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol. 4875, pp. 31–36. Springer, Heidelberg (2008), doi:10.1007/978-3-540-77537-9_6.

Robertson, N., Seymour, P.D.: Graph minors. XIII. The disjoint paths problem. Journal of Combinatorial Theory, Series B 63(1), 65–110 (1995), doi:10.1006/jctb.1995.1006

Shahrokhi, F., Sýkora, O., Székely, L.A., Vřťo, I.: Book embeddings and crossing numbers. In: Mayr, E.W., Schmidt, G., Tinhofer, G. (eds.) WG 1994. LNCS, vol. 903, pp. 256–268. Springer, Heidelberg (1995)

Shirey, R.W.: Implementation and Analysis of Efficient Graph Planarity Testing Algorithms. Ph.D. thesis, The University of Wisconsin – Madison (1969)

Wattenberg, M.: Arc diagrams: visualizing structure in strings. In: IEEE Symposium on Information Visualization (INFOVIS 2002), pp. 110–116 (2002), doi:10.1109/INFVIS.2002.1173155

Wiegers, M.: Recognizing outerplanar graphs in linear time. In: Tinhofer, G., Schmidt, G. (eds.) WG 1986. LNCS, vol. 246, pp. 165–176. Springer, Heidelberg (1987)

Yannakakis, M.: Four pages are necessary and sufficient for planar graphs. In: Proc. 18th ACM Symp. on Theory of Computing (STOC 1986), pp. 104–108 (1986), doi:10.1145/12130.12141