×

Recognizing and drawing IC-planar graphs. (English) Zbl 1342.68251

Summary: We give new results about the relationship between 1-planar graphs and RAC graphs. A graph is 1-planar if it has a drawing where each edge is crossed at most once. A graph is RAC if it can be drawn in such a way that its edges cross only at right angles. These two classes of graphs and their relationships have been widely investigated in the last years, due to their relevance in application domains where computing readable graph layouts is important to analyze or design relational data sets. We study IC-planar graphs, the sub-family of 1-planar graphs that admit 1-planar drawings with independent crossings (i.e., no two crossed edges share an endpoint). We prove that every IC-planar graph admits a straight-line RAC drawing, which may require however exponential area. If we do not require right angle crossings, we can draw every IC-planar graph with straight-line edges in linear time and quadratic area. We then study the problem of testing whether a graph is IC-planar. We prove that this problem is NP-hard, even if a rotation system for the graph is fixed. On the positive side, we describe a polynomial-time algorithm that tests whether a triangulated plane graph augmented with a given set of edges that form a matching is IC-planar.

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C10 Planar graphs; geometric and topological aspects of graph theory
05C85 Graph algorithms (graph-theoretic aspects)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ackerman, E.; Tardos, G., On the maximum number of edges in quasi-planar graphs, J. Combin. Theory Ser. A, 114, 3, 563-571 (2007) · Zbl 1120.05045
[2] Agarwal, P. K.; Aronov, B.; Pach, J.; Pollack, R.; Sharir, M., Quasi-planar graphs have a linear number of edges, Combinatorica, 17, 1, 1-9 (1997) · Zbl 0880.05050
[3] Alam, M. J.; Brandenburg, F. J.; Kobourov, S. G., Straight-line grid drawings of 3-connected 1-planar graphs, (Wismath, S. K.; Wolff, A., GD 2013. GD 2013, Lecture Notes in Comput. Sci., vol. 8242 (2013), Springer), 83-94 · Zbl 1406.68054
[4] Albertson, M. O., Chromatic number, independence ratio, and crossing number, Ars Math. Contemp., 1, 1, 1-6 (2008) · Zbl 1181.05032
[5] Argyriou, E. N.; Bekos, M. A.; Symvonis, A., Maximizing the total resolution of graphs, Comput. J., 56, 7, 887-900 (2013)
[6] Aspvall, B.; Plass, M. F.; Tarjan, R. E., A linear-time algorithm for testing the truth of certain quantified boolean formulas, Inform. Process. Lett., 8, 3, 121-123 (1979) · Zbl 0398.68042
[7] Auer, C.; Brandenburg, F. J.; Gleißner, A.; Reislhuber, J., 1-Planarity of graphs with a rotation system, J. Graph Algorithms Appl., 19, 1, 67-86 (2015) · Zbl 1307.05057
[8] Bannister, M. J.; Cabello, S.; Eppstein, D., Parameterized complexity of 1-planarity, (Dehne, F.; Solis-Oba, R.; Sack, J., WADS 2013. WADS 2013, Lecture Notes in Comput. Sci., vol. 8037 (2013), Springer), 97-108 · Zbl 1390.68329
[9] Brandenburg, F. J.; Didimo, W.; Evans, W. S.; Kindermann, P.; Liotta, G.; Montecchiani, F., Recognizing and drawing IC-planar graphs, arXiv report, available at · Zbl 1471.68189
[10] Brandenburg, F. J.; Didimo, W.; Evans, W. S.; Kindermann, P.; Liotta, G.; Montecchiani, F., Recognizing and drawing IC-planar graphs, (Lubiw, A.; Di Giacomo, E., GD 2015. GD 2015, Lecture Notes in Comput. Sci., vol. 9411 (2015), Springer), 295-308 · Zbl 1471.68189
[11] Cabello, S.; Mohar, B., Adding one edge to planar graphs makes crossing number and 1-planarity hard, SIAM J. Comput., 42, 5, 1803-1829 (2013) · Zbl 1282.05033
[12] Chrobak, M.; Payne, T. H., A linear-time algorithm for drawing a planar graph on a grid, Inform. Process. Lett., 54, 4, 241-246 (1995) · Zbl 0875.68452
[14] de Fraysseix, H.; Pach, J.; Pollack, R., Small sets supporting Fáry embeddings of planar graphs, (STOC 1988 (1988), ACM), 426-433
[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] Di Battista, G.; Eades, P.; Tamassia, R.; Tollis, I. G., Graph Drawing (1999), Prentice Hall: Prentice Hall Upper Saddle River, NJ
[17] Di Giacomo, E.; Didimo, W.; Eades, P.; Liotta, G., 2-layer right angle crossing drawings, Algorithmica, 68, 4, 954-997 (2014) · Zbl 1303.05129
[18] Di Giacomo, E.; Didimo, W.; Grilli, L.; Liotta, G.; Romeo, S. A., Heuristics for the maximum 2-layer RAC subgraph problem, Comput. J., 58, 5, 1085-1098 (2015)
[19] Di Giacomo, E.; Didimo, W.; Liotta, G.; Montecchiani, F., Area requirement of graph drawings with few crossings per edge, Comput. Geom., 46, 8, 909-916 (2013) · Zbl 1273.05151
[20] Didimo, W., Density of straight-line 1-planar graph drawings, Inform. Process. Lett., 113, 7, 236-240 (2013) · Zbl 1259.05107
[21] Didimo, W.; Eades, P.; Liotta, G., Drawing graphs with right angle crossings, Theoret. Comput. Sci., 412, 39, 5156-5166 (2011) · Zbl 1225.68134
[22] Didimo, W.; Liotta, G., Mining graph data, (Cook, D. J.; Holder, L. B., Graph Visualization and Data Mining (2007), Wiley), 35-64
[23] Didimo, W.; Liotta, G., The crossing angle resolution in graph drawing, (Pach, J., Thirty Essays on Geometric Graph Theory (2012), Springer) · Zbl 1272.05128
[24] Didimo, W.; Liotta, G.; Romeo, S. A., Topology-driven force-directed algorithms, (Brandes, U.; Cornelsen, S., GD 2010. GD 2010, Lecture Notes in Comput. Sci., vol. 6502 (2010), Springer), 165-176 · Zbl 1314.68225
[25] Didimo, W.; Liotta, G.; Romeo, S. A., A graph drawing application to web site traffic analysis, J. Graph Algorithms Appl., 15, 2, 229-251 (2011)
[26] Dolev, D.; Leighton, T.; Trickey, H., Planar embedding of planar graphs, Adv. Sci. Res., 2, 147-161 (1984)
[27] Eades, P.; Liotta, G., Right angle crossing graphs and 1-planarity, Discrete Appl. Math., 161, 7-8, 961-969 (2013) · Zbl 1408.05042
[28] Fox, J.; Pach, J.; Suk, A., The number of edges in \(k\)-quasi-planar graphs, SIAM J. Discrete Math., 27, 1, 550-561 (2013) · Zbl 1268.05051
[29] Garey, M. R.; Johnson, D. S., Crossing number is NP-complete, SIAM J. Algebr. Discrete Methods, 4, 3, 312-316 (1983) · Zbl 0536.05016
[30] Grigoriev, A.; Bodlaender, H. L., Algorithms for graphs embeddable with few crossings per edge, Algorithmica, 49, 1, 1-11 (2007) · Zbl 1131.68120
[31] Grohe, M., Computing crossing numbers in quadratic time, (Vitter, J. S.; Spirakis, P. G.; Yannakakis, M., STOC 2001 (2001), ACM), 231-236 · Zbl 1323.68314
[32] Hong, S.; Eades, P.; Liotta, G.; Poon, S., Fáry’s theorem for 1-planar graphs, (Gudmundsson, J.; Mestre, J.; Viglas, T., COCOON 2012. COCOON 2012, Lecture Notes in Comput. Sci., vol. 7434 (2012), Springer), 335-346 · Zbl 1364.68308
[33] Huang, W., Using eye tracking to investigate graph layout effects, (Hong, S.; Ma, K., APVIS 2007 (2007)), 97-100
[34] Huang, W.; Eades, P.; Hong, S., Larger crossing angles make graphs easier to read, J. Vis. Lang. Comput., 25, 4, 452-465 (2014)
[35] Huang, W.; Eades, P.; Hong, S.; Lin, C., Improving force-directed graph drawings by making compromises between aesthetics, (Hundhausen, C.; Pietriga, E., VL/HCC (2010), IEEE), 176-183
[36] Huang, W.; Hong, S.; Eades, P., Effects of crossing angles, (Fujishiro, I.; Li, H.; Ma, K., PacificVis (2008)), 41-46
[37] (Jünger, M.; Mutzel, P., Graph Drawing Software (2003), Springer) · Zbl 1029.68145
[38] (Kaufmann, M.; Wagner, D., Drawing Graphs, Methods and Models. Drawing Graphs, Methods and Models, Lecture Notes in Comput. Sci., vol. 2025 (2001), Springer) · Zbl 0977.68644
[39] Korzhik, V. P.; Mohar, B., Minimal obstructions for 1-immersions and hardness of 1-planarity testing, J. Graph Theory, 72, 1, 30-71 (2013) · Zbl 1259.05046
[40] Král, D.; Stacho, L., Coloring plane graphs with independent crossings, J. Graph Theory, 64, 3, 184-205 (2010) · Zbl 1208.05019
[41] Kynčl, J., Enumeration of simple complete topological graphs, Electron. J. Combin., 30, 7, 1676-1685 (2009) · Zbl 1228.05175
[42] Nguyen, Q.; Eades, P.; Hong, S.; Huang, W., Large crossing angles in circular layouts, (Proc. of GD 2010. Proc. of GD 2010, Lecture Notes in Comput. Sci., vol. 6502 (2010), Springer), 397-399
[43] Pach, J.; Tóth, G., Graphs drawn with few crossings per edge, Combinatorica, 17, 3, 427-439 (1997) · Zbl 0902.05017
[44] Pelsmajer, M. J.; Schaefer, M.; Stefankovic, D., Crossing numbers and parameterized complexity, (Hong, S.; Nishizeki, T.; Quan, W., GD 2007. GD 2007, Lecture Notes in Comput. Sci., vol. 4875 (2007), Springer), 31-36 · Zbl 1137.68502
[45] Purchase, H. C., Effective information visualisation: a study of graph drawing aesthetics and algorithms, Interact. Comput., 13, 2, 147-162 (2000)
[46] 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
[47] Ringel, G., Ein Sechsfarbenproblem auf der Kugel, Abh. Math. Semin. Univ. Hambg., 29, 1-2, 107-117 (1965) · Zbl 0132.20701
[48] Sugiyama, K., Graph Drawing and Applications for Software and Knowledge Engineers (2002), World Scientific · Zbl 1011.68068
[49] (Tamassia, R., Handbook of Graph Drawing and Visualization (2013), CRC Press) · Zbl 1275.68033
[50] Thomassen, C., Rectilinear drawings of graphs, J. Graph Theory, 12, 3, 335-341 (1988) · Zbl 0649.05051
[51] Vignelli, M., New York subway map
[52] Ware, C.; Purchase, H. C.; Colpoys, L.; McGill, M., Cognitive measurements of graph aesthetics, Inf. Vis., 1, 2, 103-110 (2002)
[53] Zhang, X., Drawing complete multipartite graphs on the plane with restrictions on crossings, Acta Math. Sin., 30, 12, 2045-2053 (2014) · Zbl 1304.05031
[54] Zhang, X.; Liu, G., The structure of plane graphs with independent crossings and its applications to coloring problems, Cent. Eur. J. Math., 11, 2, 308-321 (2013) · Zbl 1258.05028
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.