×

Compact drawings of 1-planar graphs with right-angle crossings and few bends. (English) Zbl 1468.68146

Summary: We study the following classes of beyond-planar graphs: 1-planar, IC-planar, and NIC-planar graphs. These are the graphs that admit a 1-planar, IC-planar, and NIC-planar drawing, respectively. A drawing of a graph is 1-planar if every edge is crossed at most once. A 1-planar drawing is IC-planar if no two pairs of crossing edges share a vertex. A 1-planar drawing is NIC-planar if no two pairs of crossing edges share two vertices. We study the relations of these beyond-planar graph classes (beyond-planar graphs is a collective term for the primary attempts to generalize the planar graphs) to right-angle crossing (RAC) graphs that admit compact drawings on the grid with few bends. We present four drawing algorithms that preserve the given embeddings. First, we show that every \(n\)-vertex NIC-planar graph admits a NIC-planar RAC drawing with at most one bend per edge on a grid of size \(\mathcal{O}(n) \times \mathcal{O}(n)\). Then, we show that every \(n\)-vertex 1-planar graph admits a 1-planar RAC drawing with at most two bends per edge on a grid of size \(\mathcal{O}(n^3) \times \mathcal{O}(n^3)\). Finally, we make two known algorithms embedding-preserving; for drawing 1-planar RAC graphs with at most one bend per edge and for drawing IC-planar RAC graphs straight-line.

MSC:

68R10 Graph theory (including graph drawing) in computer science
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)

Software:

Algorithm 447
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Chaplick, S.; Lipp, F.; Wolff, A.; Zink, J., Compact drawings of 1-planar graphs with right-angle crossings and few bends, (Biedl, T.; Kerren, A., Proc. 26th Int. Symp. Graph Drawing & Network Vis.. Proc. 26th Int. Symp. Graph Drawing & Network Vis., GD’18. Proc. 26th Int. Symp. Graph Drawing & Network Vis.. Proc. 26th Int. Symp. Graph Drawing & Network Vis., GD’18, LNCS, vol. 11282 (2018), Springer), 137-151 · Zbl 1468.68145
[2] Purchase, H. C., Effective information visualisation: a study of graph drawing aesthetics and algorithms, Interact. Comput., 13, 2, 147-162 (2000)
[3] Purchase, H. C.; Carrington, D. A.; Allder, J., Empirical evaluation of aesthetics-based graph layout, Empir. Softw. Eng., 7, 3, 233-255 (2002) · Zbl 1010.68636
[4] Ware, C.; Purchase, H. C.; Colpoys, L.; McGill, M., Cognitive measurements of graph aesthetics, Inf. Vis., 1, 2, 103-110 (2002)
[5] Purchase, H. C., Which aesthetic has the greatest effect on human understanding?, (Battista, G. D., Proc. 5th Int. Symp. Graph Drawing. Proc. 5th Int. Symp. Graph Drawing, GD’97. Proc. 5th Int. Symp. Graph Drawing. Proc. 5th Int. Symp. Graph Drawing, GD’97, LNCS, vol. 1353 (1997), Springer), 248-261
[6] Huang, W., Using eye tracking to investigate graph layout effects, (Hong, S.; Ma, K., Proc. 6th Int. Asia-Pacific Symp. Visual.. Proc. 6th Int. Asia-Pacific Symp. Visual., APVIS’07 (2007), IEEE), 97-100
[7] Huang, W.; Eades, P.; Hong, S., Larger crossing angles make graphs easier to read, J. Vis. Lang. Comput., 25, 4, 452-465 (2014)
[8] Huang, W.; Hong, S.; Eades, P., Effects of crossing angles, (Proc. IEEE VGTC Pacific Visualization Symposium. Proc. IEEE VGTC Pacific Visualization Symposium, PacificVis’08 (2008)), 41-46
[9] Hoffmann, M.; van Kreveld, M. J.; Kusters, V.; Rote, G., Quality ratios of measures for graph drawing styles, (Proc. 26th Canad. Conf. Comput. Geom.. Proc. 26th Canad. Conf. Comput. Geom., CCCG’14 (2014)), 33-39
[10] Ringel, G., Ein Sechsfarbenproblem auf der Kugel, Abh. Math. Semin. Univ. Hamb., 29, 1-2, 107-117 (1965) · Zbl 0132.20701
[11] Kobourov, S. G.; Liotta, G.; Montecchiani, F., An annotated bibliography on 1-planarity, Comput. Sci. Rev., 25, 49-67 (2017) · Zbl 1398.68402
[12] Didimo, W.; Eades, P.; Liotta, G., Drawing graphs with right angle crossings, Theor. Comput. Sci., 412, 39, 5156-5166 (2011) · Zbl 1225.68134
[13] Didimo, W.; Liotta, G.; Montecchiani, F., A survey on graph drawing beyond planarity, ACM Comput. Surv., 52, 1, 4:1-4:37 (2019)
[14] Schnyder, W., Embedding planar graphs on the grid, (Johnson, D. S., Proc. 1st ACM-SIAM Symp. Discrete Algorithms. Proc. 1st ACM-SIAM Symp. Discrete Algorithms, SODA’90 (1990)), 138-148 · Zbl 0786.05029
[15] de Fraysseix, H.; Pach, J.; Pollack, R., How to draw a planar graph on a grid, Combinatorica, 10, 1, 41-51 (1990) · Zbl 0728.05016
[16] Brandenburg, F. J.; Didimo, W.; Evans, W. S.; Kindermann, P.; Liotta, G.; Montecchiani, F., Recognizing and drawing IC-planar graphs, Theor. Comput. Sci., 636, 1-16 (2016) · Zbl 1342.68251
[17] Eades, P.; Liotta, G., Right angle crossing graphs and 1-planarity, Discrete Appl. Math., 161, 7-8, 961-969 (2013) · Zbl 1408.05042
[18] Bachmaier, C.; Brandenburg, F. J.; Hanauer, K.; Neuwirth, D.; Reislhuber, J., NIC-planar graphs, Discrete Appl. Math., 232, 23-40 (2017) · Zbl 1372.05047
[19] Bekos, M. A.; 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
[20] Harel, D.; Sardas, M., An algorithm for straight-line drawing of planar graphs, Algorithmica, 20, 2, 119-135 (1998) · Zbl 0895.68105
[21] Chrobak, M.; Payne, T. H., A linear-time algorithm for drawing a planar graph on a grid, Inf. Process. Lett., 54, 4, 241-246 (1995) · Zbl 0875.68452
[22] Liotta, G.; Montecchiani, F., L-visibility drawings of IC-planar graphs, Inf. Process. Lett., 116, 3, 217-222 (2016) · Zbl 1328.68263
[23] Thomassen, C., Rectilinear drawings of graphs, J. Graph Theory, 12, 3, 335-341 (1988) · Zbl 0649.05051
[24] Hopcroft, J. E.; Tarjan, R. E., Algorithm 447: efficient algorithms for graph manipulation, Commun. ACM, 16, 6, 372-378 (1973)
[25] Zink, J., 1-Planar RAC Drawings with Bends (2017), Institut für Informatik, Universität Würzburg, Master’s thesis
[26] Czap, J.; Šugerek, P., Three classes of 1-planar graphs (2014)
[27] Zhang, X., Drawing complete multipartite graphs on the plane with restrictions on crossings, Acta Math. Sin. Engl. Ser., 30, 12, 2045-2053 (2014) · Zbl 1304.05031
[28] Zink, J., Java source code: drawing embedded graphs with right-angled crossings (2018), GitHub repository
[29] Farey sequence (“2018), wikipedia, the free encyclopedia, online
[30] Czap, J.; Hudák, D., On drawings and decompositions of 1-planar graphs, Electron. J. Comb., 20, 2, 54 (2013) · Zbl 1295.05084
[31] Chiba, N.; Yamanouchi, T.; Nishizeki, T., Linear algorithms for convex drawings of planar graphs, (Bondy, J.; Murty, U., Progress in Graph Theory (1984), Academic Press: Academic Press Toronto), 153-173 · Zbl 0556.05023
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.