×

Simple \(k\)-planar graphs are simple \((k + 1)\)-quasiplanar. (English) Zbl 1436.05031

Summary: A simple topological graph is \(k\)-quasiplanar \((k\geq 2)\) if it contains no \(k\) pairwise crossing edges, and \(k\)-planar if no edge is crossed more than \(k\) times. In this paper, we explore the relationship between \(k\)-planarity and \(k\)-quasiplanarity to show that, for \(k\geq 2\), every \(k\)-planar simple topological graph can be transformed into a \((k+1)\)-quasiplanar simple topological graph.

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
05C62 Graph representations (geometric and intersection representations, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ackerman, E., On the maximum number of edges in topological graphs with no four pairwise crossing edges, Discrete Comput. Geom., 41, 3, 365-375 (2009) · Zbl 1161.05313
[2] Ackerman, E., On topological graphs with at most four crossings per edge (2015), CoRR
[3] Ackerman, E.; Fox, J.; Pach, J.; Suk, A., On grids in topological graphs, Comput. Geom., 47, 7, 710-723 (2014) · Zbl 1292.05087
[4] 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
[5] 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
[6] Angelini, P.; Bekos, M. A.; Brandenburg, F. J.; Da Lozzo, G.; Di Battista, G.; Didimo, W.; Liotta, G.; Montecchiani, F.; Rutter, I., On the relationship between k-planar and k-quasi-planar graphs, (Graph-Theoretic Concepts in Computer Science. Graph-Theoretic Concepts in Computer Science, LNCS, vol. 10520 (2017), Springer), 59-74 · Zbl 1483.05044
[7] Bae, S. W.; Baffier, J.-F.; Chun, J.; Eades, P.; Eickmeyer, K.; Grilli, L.; Hong, S.-H.; Korman, M.; Montecchiani, F.; Rutter, I.; Tóth, C. D., Gap-planar graphs, Theoret. Comput. Sci. (2018) · Zbl 1400.68151
[8] Bekos, M. A.; Kaufmann, M.; Raftopoulou, C. N., On the density of non-simple 3-planar graphs, (Graph Drawing and Network Visualization. Graph Drawing and Network Visualization, LNCS, vol. 9801 (2016), Springer), 344-356 · Zbl 1483.68249
[9] Bekos, M. A.; Kaufmann, M.; Raftopoulou, C. N., On optimal 2- and 3-planar graphs, (Symposium on Computational Geometry. Symposium on Computational Geometry, LIPIcs, vol. 77 (2017), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik), Article 16 pp. · Zbl 1435.05057
[10] Binucci, C.; Chimani, M.; Didimo, W.; Gronemann, M.; Klein, K.; Kratochvíl, J.; Montecchiani, F.; Tollis, I. G., Algorithms and characterizations for 2-layer fan-planarity: from caterpillar to stegosaurus, J. Graph Algorithms Appl., 21, 1, 81-102 (2017) · Zbl 1358.05194
[11] Binucci, C.; Di Giacomo, E.; Didimo, W.; Montecchiani, F.; Patrignani, M.; Symvonis, A.; Tollis, I. G., Fan-planarity: properties and complexity, Theoret. Comput. Sci., 589, 76-86 (2015) · Zbl 1317.68134
[12] Brandenburg, F. J.; Didimo, W.; Evans, W. S.; Kindermann, P.; Liotta, G.; Montecchiani, F., Recognizing and drawing IC-planar graphs, Theoret. Comput. Sci., 636, 1-16 (2016) · Zbl 1342.68251
[13] Capoyleas, V.; Pach, J., A Turán-type theorem on chords of a convex polygon, J. Combin. Theory Ser. B, 56, 1, 9-15 (1992) · Zbl 0783.05032
[14] Cheong, O.; Har-Peled, S.; Kim, H.; Kim, H., On the number of edges of fan-crossing free graphs, Algorithmica, 73, 4, 673-695 (2015) · Zbl 1330.05048
[15] Didimo, W.; Liotta, G.; Montecchiani, F., A survey on graph drawing beyond planarity, ACM Comput. Surv., 52, 1, Article 4 pp. (2019)
[16] Eades, P.; Liotta, G., Right angle crossing graphs and 1-planarity, Discrete Appl. Math., 161, 7-8, 961-969 (2013) · Zbl 1408.05042
[17] Fox, J.; Pach, J., Coloring \(K_k\)-free intersection graphs of geometric objects in the plane, (Symposium on Computational Geometry (2008), ACM), 346-354 · Zbl 1271.05032
[18] 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
[19] Hoffmann, M.; Tóth, C. D., Two-planar graphs are quasiplanar, (MFCS. MFCS, LIPIcs, vol. 83 (2017), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik), Article 47 pp. · Zbl 1441.68187
[20] Kaufmann, M.; Ueckerdt, T., The density of fan-planar graphs (2014), CoRR
[21] Pach, J.; Pinchasi, R.; Sharir, M.; Tóth, G., Topological graphs with no large grids, Graphs Combin., 21, 3, 355-364 (2005) · Zbl 1075.05027
[22] Pach, J.; Radoičić, R.; Tardos, G.; Tóth, G., Improving the crossing lemma by finding more crossings in sparse graphs, Discrete Comput. Geom., 36, 4, 527-552 (2006) · Zbl 1104.05022
[23] Pach, J.; Radoičić, R.; Tóth, G., Relaxing planarity for topological graphs, (Japanese Conf. Discrete Comput. Geom.. Japanese Conf. Discrete Comput. Geom., LNCS, vol. 2866 (2003), Springer), 221-232 · Zbl 1179.05036
[24] Pach, J.; Shahrokhi, F.; Szegedy, M., Applications of the crossing number, Algorithmica, 16, 1, 111-117 (1996) · Zbl 0851.68088
[25] Pach, J.; Tóth, G., Graphs drawn with few crossings per edge, Combinatorica, 17, 3, 427-439 (1997) · Zbl 0902.05017
[26] Suk, A.; Walczak, B., New bounds on the maximum number of edges in k-quasi-planar graphs, Comput. Geom., 50, 24-33 (2015) · Zbl 1328.05056
[27] Valtr, P., On geometric graphs with no k pairwise parallel edges, Discrete Comput. Geom., 19, 3, 461-469 (1998) · Zbl 0908.05035
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.