×

Parameterized algorithms for fixed-order book drawing with few crossings per edge. (English) Zbl 1543.05140

Summary: Given an \(n\)-vertex graph \(G\) with a fixed linear ordering of \(V(G)\) and two integers \(k\), \(b\), the problem fixed-order book drawing with few crossings per edge asks whether or not \(G\) admits a \(k\)-page book drawing where the maximum number of crossings per edge can be upper bounded by the number \(b\). This problem was posed as an open question by S. Bhore et al. [J. Graph Algorithms Appl. 24, No. 4, 603–620 (2020; Zbl 1451.05222)]. In this paper, we study this problem from the viewpoint of parameterized complexity, in particular, we develop fixed-parameter tractable algorithms for it. More specifically, we show that this problem parameterized by both the bound number \(b\) of crossings per edge and the vertex cover number \(\tau\) of the input graph admits an algorithm with running time in \((b+2)^{\mathcal{O}(\tau^3)}\cdot n\), and this problem parameterized by both the bound number \(b\) of crossings per edge and the pathwidth \(\kappa\) of the vertex ordering admits an algorithm with running time in \((b+2)^{\mathcal{O}(\kappa^2)}\cdot n\). Our results provide a specific answer to Bhore et al.’s question [loc. cit.].

MSC:

05C62 Graph representations (geometric and intersection representations, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity

Citations:

Zbl 1451.05222
Full Text: DOI

References:

[1] Angelini, P., Bekos, M. A., Kaufmann, M. and Montecchiani, F., On 3D visibility representations of graphs with few crossings per edge, Theoret. Comput. Sci.784(13) (2019) 11-20. · Zbl 1423.68325
[2] Bannister, M. J. and Eppstein, D., Crossing minimization for 1-page and 2-page drawing of graphs with bounded treewidth, Proc. GD’14, eds. Duncan, C. and Symvonis, A., , Vol. 8871 (Springer, Heidelberg, 2014), pp. 210-221. · Zbl 1426.68199
[3] Bannister, M. J., Eppstein, D. and Simons, J. A., Fixed parameter tractability of crossing minimization of almost-trees, Proc. GD’13, eds. Wismath, S. and Wolff, A., , Vol. 8242 (Springer, Heidelberg, 2013), pp. 340-351. · Zbl 1406.68061
[4] Bhore, S., Ganian, R., Montecchiani, F. and Nöllenburg, M., Parameterized algorithms for book embedding problems, J. Graph Algorithms Appl.24(4) (2020) 603-620. · Zbl 1451.05222
[5] Bhore, S., Ganian, R., Montecchiani, F. and Nöllenburg, M., Parameterized algorithms for queue layouts, J. Graph Algorithms Appl.26(3) (2022) 335-352. · Zbl 1498.05257
[6] Binucci, C., Di Giacomoa, E., Hossainb, M. I. and Liotta, G., 1-page and 2-page drawings with bounded number of crossings per edge, Eur. J. Combin.68 (2018) 24-37. · Zbl 1373.05123
[7] Buchheim, C. and Zheng, L., Fixed linear crossing minimization by reduction to the maximum cut problem, Proc. COCOON’06, eds. Chen, D. Z. and Lee, D. T., , Vol. 4112 (Springer, 2006), pp. 507-516. · Zbl 1162.68492
[8] Chen, J., Kanj, I. A. and Xia, G., Improved upper bounds for vertex cover, Theoret. Comput. Sci.411(40-42) (2010) 3736-3756. · Zbl 1205.05217
[9] Cimikowski, R., Algorithms for the fixed linear crossing number problem, Discrete Appl. Math.122(1-3) (2002) 93-115. · Zbl 1002.68194
[10] Cimikowski, R., An analysis of some linear graph layout heuristics, J. Heuristics12(3) (2006) 143-153. · Zbl 1163.90809
[11] Cimikowski, R. and Mumey, B., Approximating the fixed linear crossing number, Discrete Appl. Math.155(17) (2007) 2202-2210. · Zbl 1127.68116
[12] Da Lozzo, G., Eppstein, D., Goodrich, M. T. and Gupta, S., Subexponential-time and FPT algorithms for embedded flat clustered planarity, Proc. WG’18, eds. Brandstadt, A., Kohler, E. and Meer, K., , Vol. 11159 (Springer, Cham, 2018), pp. 111-124. · Zbl 1517.68287
[13] Di Giacomo, E., Didimo, W., Liotta, G. and Montecchiani, F., Area requirement of graph drawings with few crossing per edge, Comput. Geom.: Theor. Appl.46(8) (2013) 909-916. · Zbl 1273.05151
[14] Di Giacomo, E., Liotta, G. and Montecchiani, F., Sketched representations and orthogonal planarity of bounded treewidth graphs, Proc. GD’19, eds. Archambault, D. and Tóth, C. D., , Vol. 11904 (Springer, Cham, 2019), pp. 379-392. · Zbl 1542.68139
[15] Downey, R. G. and Fellows, M. R., Fundamentals of parameterized complexity, Texts in Comput. Sci. (Springer, 2013). · Zbl 1358.68006
[16] Garey, M. R., Johnson, D. S., Miller, G. L. and Papadimitriou, C. H., The complexity of coloring circular arcs and chords, SIAM J. Algebratic and Discrete Methods1(2) (1980) 216-227. · Zbl 0499.05058
[17] Grigoriev, A. and Bodlaender, H. L., Algorithms for graphs embeddable with few crossings per edge, Algorithmica49(1) (2007) 1-11. · Zbl 1131.68120
[18] Hliněný, P. and Sankaran, A., Exact crossing number parameterized by vertex cover, Proc. GD’19, eds. Archambault, D. and Tóth, C. D., , Vol. 11904 (Springer, Cham, 2019), pp. 307-319. · Zbl 1539.68223
[19] Kinnersley, N. G., The vertex separation number of a graph equals its pathwidth, Inform. Process. Lett.42(6) (1992) 345-350. · Zbl 0764.68121
[20] Klawitter, J., Mchedlidze, T. and Nöllenburg, M., Experimental evaluation of book drawing algorithms, Proc. GD’17, eds. Frati, F. and Ma, K.-L., , Vol. 10692 (Springer, Cham, 2018), pp. 224-238. · Zbl 1503.68225
[21] Liu, Y., Chen, J., Huang, J. and Wang, J., On parameterized algorithms for fixed-order book thickness with respect to the pathwidth of the vertex ordering, Theoret. Comput. Sci.873 (2021) 16-24. · Zbl 1482.68178
[22] Liu, Y., Chen, J. and Huang, J., On book thickness parameterized by the vertex cover number, Sci. China Inform. Sci., 65 (2022) 140603:1-140603:2.
[23] Liu, Y., Li, Y. and Huang, J., Fixed-parameter tractability for book drawing with bounded number of crossings per edge, Proc. AAIM’21, eds. Wu, W. and Du, H., , Vol. 13153 (Springer, Cham, 2021), pp. 438-449. · Zbl 1502.68239
[24] Liu, Y., Li, Y. and Huang, J., Vertex-bipartition: A unified approach for kernelization of graph linear layout problems parameterized by vertex cover, Int. J. Found. Comput. Sci. (2023) https://doi.org/10.1142/S0129054123410022
[25] Masuda, S., Nakajima, K., Kashiwabara, T. and Fujisawa, T., Crossing minimization in linear embeddings of graphs, IEEE T. Comput.39(1) (1990) 124-127. · Zbl 1395.68215
[26] Unger, W., On the \(k\)-colouring of circle-graphs, Proc. STACS’88, eds. Cori, R. and Wirsing, M., , Vol. 294 (Springer, Heidelberg, 1988), pp. 61-72. · Zbl 0644.68094
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.