Fixed-parameter algorithms for computing RAC drawings of graphs. (English) Zbl 07925711
Bekos, Michael A. (ed.) et al., Graph drawing and network visualization. 31st international symposium, GD 2023, Isola delle Femmine, Palermo, Italy, September 20–22, 2023. Revised selected papers. Part II. Cham: Springer. Lect. Notes Comput. Sci. 14466, 66-81 (2023).
Summary: In a right-angle crossing (RAC) drawing of a graph, each edge is represented as a polyline and edge crossings must occur at an angle of exactly \(90^\circ \), where the number of bends on such polylines is typically restricted in some way. While structural and topological properties of RAC drawings have been the focus of extensive research, little was known about the boundaries of tractability for computing such drawings. In this paper, we initiate the study of RAC drawings from the viewpoint of parameterized complexity. In particular, we establish that computing a RAC drawing of an input graph \(G\) with at most \(b\) bends (or determining that none exists) is fixed-parameter tractable parameterized by either the feedback edge number of \(G\), or \(b\) plus the vertex cover number of \(G\).
For the entire collection see [Zbl 07831429].
For the entire collection see [Zbl 07831429].
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
References:
| [1] | Angelini, P.; Bekos, MA; Förster, H.; Kaufmann, M., On RAC drawings of graphs with one bend per edge, Theor. Comput. Sci., 828-829, 42-54, 2020 · Zbl 1443.68117 · doi:10.1016/j.tcs.2020.04.018 |
| [2] | Angelini, P., Bekos, M.A., Katheder, J., Kaufmann, M., Pfister, M.: RAC drawings of graphs with low degree. In: Szeider, S., Ganian, R., Silva, A. (eds.) 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022, August 22-26, 2022, Vienna, Austria. LIPIcs, vol. 241, pp. 11:1-11:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022). doi:10.4230/LIPIcs.MFCS.2022.11 |
| [3] | Angelini, P., On the perspectives opened by right angle crossing drawings, J. Graph Algorithms Appl., 15, 1, 53-78, 2011 · Zbl 1217.05063 · doi:10.7155/jgaa.00217 |
| [4] | Argyriou, EN; Bekos, MA; Symvonis, A., The straight-line RAC drawing problem is np-hard, J. Graph Algorithms Appl., 16, 2, 569-597, 2012 · Zbl 1254.05120 · doi:10.7155/jgaa.00274 |
| [5] | Balko, M., et al.: Bounding and computing obstacle numbers of graphs. In: Chechik, S., Navarro, G., Rotenberg, E., Herman, G. (eds.) 30th Annual European Symposium on Algorithms, ESA 2022, September 5-9, 2022, Berlin/Potsdam, Germany. LIPIcs, vol. 244, pp. 11:1-11:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022). doi:10.4230/LIPIcs.ESA.2022.11 |
| [6] | Bannister, MJ; Cabello, S.; Eppstein, D., Parameterized complexity of 1-planarity, J. Graph Algorithms Appl., 22, 1, 23-49, 2018 · Zbl 1377.05118 · doi:10.7155/jgaa.00457 |
| [7] | Basu, S., Pollack, R., Roy, M.F.: Algorithms in Real Algebraic geometry, Algorithms and Computation in Mathematics, vol. 10. Springer, Cham (2006). doi:10.1007/3-540-33099-2, http://link.springer.com/10.1007/3-540-33099-2 · Zbl 1102.14041 |
| [8] | Bekos, MA; Didimo, W.; Liotta, G.; Mehrabi, S.; Montecchiani, F., On RAC drawings of 1-planar graphs, Theor. Comput. Sci., 689, 48-57, 2017 · Zbl 1372.68202 · doi:10.1016/j.tcs.2017.05.039 |
| [9] | Bhore, S.; Ganian, R.; Montecchiani, F.; Nöllenburg, M., Parameterized algorithms for book embedding problems, J. Graph Algorithms Appl., 24, 4, 603-620, 2020 · Zbl 1451.05222 · doi:10.7155/jgaa.00526 |
| [10] | Bhore, S.; Ganian, R.; Montecchiani, F.; Nöllenburg, M., Parameterized algorithms for queue layouts, J. Graph Algorithms Appl., 26, 3, 335-352, 2022 · Zbl 1498.05257 · doi:10.7155/jgaa.00597 |
| [11] | Bieker, N.: Complexity of graph drawing problems in relation to the existential theory of the reals. Ph.D. thesis, Bachelor’s thesis, Karlsruhe Institute of Technology (August 2020) (2020) |
| [12] | Brand, C., Ceylan, E., Ganian, R., Hatschka, C., Korchemna, V.: Edge-cut width: An algorithmically driven analogue of treewidth based on edge cuts. In: Bekos, M.A., Kaufmann, M. (eds.) Graph-Theoretic Concepts in Computer Science - 48th International Workshop, WG 2022, Tübingen, Germany, June 22-24, 2022, Revised Selected Papers. LNCS, vol. 13453, pp. 98-113. Springer, Cham (2022). doi:10.1007/978-3-031-15914-5_8 · Zbl 07682404 |
| [13] | Chen, J.; Kanj, IA; Xia, G., Improved upper bounds for vertex cover, Theor. Comput. Sci., 411, 40-42, 3736-3756, 2010 · Zbl 1205.05217 · doi:10.1016/j.tcs.2010.06.026 |
| [14] | Courcelle, B.; Makowsky, JA; Rotics, U., Linear time solvable optimization problems on graphs of bounded clique-width, Theory Comput. Syst., 33, 2, 125-150, 2000 · Zbl 1009.68102 · doi:10.1007/s002249910009 |
| [15] | Cygan, M., et al.: Parameterized Algorithms. 1st edn. Springer Publishing Company, Inc., Berlin (2015). doi:10.1007/978-3-319-21275-3 · Zbl 1334.90001 |
| [16] | Di Giacomo, E.; Didimo, W.; Eades, P.; Liotta, G., 2-layer right angle crossing drawings, Algorithmica, 68, 4, 954-997, 2014 · Zbl 1303.05129 · doi:10.1007/s00453-012-9706-7 |
| [17] | Di Giacomo, E.; Didimo, W.; Grilli, L.; Liotta, G.; Romeo, SA, Heuristics for the maximum 2-layer RAC subgraph problem, Comput. J., 58, 5, 1085-1098, 2015 · doi:10.1093/comjnl/bxu017 |
| [18] | Didimo, W.; Hong, S-H; Tokuyama, T., Right angle crossing drawings of graphs, Beyond Planar Graphs, 149-169, 2020, Singapore: Springer, Singapore · Zbl 07374190 · doi:10.1007/978-981-15-6533-5_9 |
| [19] | Didimo, W.; Eades, P.; Liotta, G., A characterization of complete bipartite RAC graphs, Inf. Process. Lett., 110, 16, 687-691, 2010 · Zbl 1234.68324 · doi:10.1016/j.ipl.2010.05.023 |
| [20] | Didimo, W.; Eades, P.; Liotta, G., Drawing graphs with right angle crossings, Theoret. Comput. Sci., 412, 39, 5156-5166, 2011 · Zbl 1225.68134 · doi:10.1016/j.tcs.2011.05.025 |
| [21] | Didimo, W.; Liotta, G.; Montecchiani, F., A survey on graph drawing beyond planarity, ACM Comput. Surv., 52, 1, 4:1-4:37, 2019 · doi:10.1145/3301281 |
| [22] | Diestel, R.: Graph Theory. 5th Edn., Graduate Texts in Mathematics, vol. 173. Springer, Cham (2017). doi:10.1007/978-3-662-53622-3 · Zbl 1375.05002 |
| [23] | Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science, Springer, London (2013). doi:10.1007/978-1-4471-5559-1 · Zbl 1358.68006 |
| [24] | Eiben, E., Ganian, R., Hamm, T., Klute, F., Nöllenburg, M.: Extending nearly complete 1-planar drawings in polynomial time. In: Esparza, J., Král’, D. (eds.) 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020, August 24-28, 2020, Prague, Czech Republic. LIPIcs, vol. 170, pp. 31:1-31:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020). doi:10.4230/LIPIcs.MFCS.2020.31 · Zbl 07559402 |
| [25] | Eiben, E., Ganian, R., Hamm, T., Klute, F., Nöllenburg, M.: Extending partial 1-planar drawings. In: Czumaj, A., Dawar, A., Merelli, E. (eds.) 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference). LIPIcs, vol. 168, pp. 43:1-43:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020). doi:10.4230/LIPIcs.ICALP.2020.43 · Zbl 07559402 |
| [26] | Fleszar, K.; Mnich, M.; Spoerhase, J., New algorithms for maximum disjoint paths based on tree-likeness, Math. Program., 171, 1-2, 433-461, 2018 · Zbl 1401.68361 · doi:10.1007/s10107-017-1199-3 |
| [27] | Förster, H., Kaufmann, M.: On compact RAC drawings. In: Grandoni, F., Herman, G., Sanders, P. (eds.) 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference). LIPIcs, vol. 173, pp. 53:1-53:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020). doi:10.4230/LIPIcs.ESA.2020.53 · Zbl 07651192 |
| [28] | de Fraysseix, H., Pach, J., Pollack, R.: Small sets supporting fáry embeddings of planar graphs. In: Simon, J. (ed.) Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA, pp. 426-433. ACM (1988). doi:10.1145/62212.62254 |
| [29] | Fáry, I., On straight lines representation of planar graphs, Acta Sci. Math. (Szeged), 11, 229-233, 1948 · Zbl 0030.17902 |
| [30] | Ganian, R.: Using neighborhood diversity to solve hard problems. CoRR abs/1201.3091 (2012). doi:10.48550/arXiv.1201.3091 |
| [31] | Ganian, R., Korchemna, V.: Slim tree-cut width. In: Dell, H., Nederlof, J. (eds.) 17th International Symposium on Parameterized and Exact Computation, IPEC 2022, September 7-9, 2022, Potsdam, Germany. LIPIcs, vol. 249, pp. 15:1-15:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022). doi:10.4230/LIPIcs.IPEC.2022.15 |
| [32] | Ganian, R.; Ordyniak, S., The power of cut-based parameters for computing edge-disjoint paths, Algorithmica, 83, 2, 726-752, 2021 · Zbl 1512.68220 · doi:10.1007/s00453-020-00772-w |
| [33] | Garey, MR; Johnson, DS, Crossing number is np-complete, SIAM J. Algebraic Discret. Methods, 4, 3, 312-316, 1983 · Zbl 0536.05016 · doi:10.1137/0604033 |
| [34] | Grohe, M., Computing crossing numbers in quadratic time, J. Comput. Syst. Sci., 68, 2, 285-302, 2004 · Zbl 1073.68064 · doi:10.1016/j.jcss.2003.07.008 |
| [35] | Hlinený, P., Sankaran, A.: Exact crossing number parameterized by vertex cover. In: Archambault, D., Tóth, C.D. (eds.) Graph Drawing and Network Visualization - 27th International Symposium, GD 2019, Prague, Czech Republic, September 17-20, 2019, Proceedings. LNCS, vol. 11904, pp. 307-319. Springer (2019). doi:10.1007/978-3-030-35802-0_24 · Zbl 1539.68223 |
| [36] | Huang, W.: Using eye tracking to investigate graph layout effects. In: Hong, S., Ma, K. (eds.) APVIS 2007, 6th International Asia-Pacific Symposium on Visualization 2007, Sydney, Australia, 5-7 February 2007, pp. 97-100. IEEE Computer Society (2007). doi:10.1109/APVIS.2007.329282 |
| [37] | Huang, W., Eades, P., Hong, S.: Larger crossing angles make graphs easier to read. J. Vis. Lang. Comput. 25(4), 452-465 (2014). doi:10.1016/j.jvlc.2014.03.001 |
| [38] | Huang, W., Hong, S., Eades, P.: Effects of crossing angles. In: IEEE VGTC Pacific Visualization Symposium 2008, PacificVis 2008, Kyoto, Japan, March 5-7, 2008, pp. 41-46. IEEE Computer Society (2008). doi:10.1109/PACIFICVIS.2008.4475457 |
| [39] | Knop, D.; Koutecký, M.; Masarík, T.; Toufar, T., Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity, Log. Methods Comput. Sci., 15, 4, 1-32, 2019 · Zbl 1427.68125 · doi:10.23638/LMCS-15(4:12)2019 |
| [40] | Lampis, M.: Algorithmic meta-theorems for restrictions of treewidth. In: de Berg, M., Meyer, U. (eds.) Algorithms - ESA 2010, 18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part I. LNCS, vol. 6346, pp. 549-560. Springer, Cham (2010). doi:10.1007/978-3-642-15775-2_47 · Zbl 1287.68078 |
| [41] | Mutzel, P., An alternative method to crossing minimization on hierarchical graphs, SIAM J. Optim., 11, 4, 1065-1080, 2001 · Zbl 1010.90098 · doi:10.1137/S1052623498334013 |
| [42] | Nešetřil, J., Ossona de Mendez, P.: Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, vol. 28. Springer, Heidelberg (2015). doi:10.1007/978-3-642-27875-4 · Zbl 1268.05002 |
| [43] | Robertson, N., Seymour, P.D.: Graph minors. III. Planar Tree-width. J. Comb. Theory, Ser. B. 36(1), 49-64 (1984). doi:10.1016/0095-8956(84)90013-3 · Zbl 0548.05025 |
| [44] | Schaefer, M.: RAC-drawability is \(\exists \mathbb{R} \)-complete. In: Graph Drawing and Network Visualization: 29th International Symposium, GD 2021, Tübingen, Germany, September 14-17, 2021, Revised Selected Papers, pp. 72-86. Springer-Verlag, Heidelberg (2021). doi:10.1007/978-3-030-92931-2_5 · Zbl 07551734 |
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.
