Fan-planarity: properties and complexity. (English) Zbl 1317.68134
Summary: In a fan-planar drawing of a graph an edge can cross only edges with a common end-vertex. Fan-planar drawings have been recently introduced by M. Kaufmann and T. Ueckerdt [“The density of fan-planar graphs”, Preprint, arXiv:1403.6184], who proved that every \(n\)-vertex fan-planar drawing has at most \(5n-10\) edges, and that this bound is tight for \(n \geq 20\). We extend their result from both the combinatorial and the algorithmic point of view. We prove tight bounds on the density of constrained versions of fan-planar drawings and study the relationship between fan-planarity and \(k\)-planarity. Also, we prove that testing fan-planarity in the variable embedding setting is NP-complete.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
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.; Fulek, R.; Tóth, C. D., Graphs that admit polyline drawings with few crossing angles, SIAM J. Discrete Math., 26, 1, 305-320 (2012) · Zbl 1245.05024 |
| [3] | 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 |
| [4] | 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 |
| [5] | Alam, M. J.; Brandenburg, F. J.; Kobourov, S. G., Straight-line grid drawings of 3-connected 1-planar graphs, (GD. GD, LNCS, vol. 8242 (2013)), 83-94 · Zbl 1406.68054 |
| [6] | Angelini, P.; Di Battista, G.; Didimo, W.; Frati, F.; Hong, S.-H.; Kaufmann, M.; Liotta, G.; Lubiw, A., Large angle crossing drawings of planar graphs in subquadratic area, (EGC. EGC, LNCS, vol. 7579 (2011)), 200-209 · Zbl 1374.68348 |
| [7] | Asano, K., The crossing number of \(K_{1, 3, n}\) and \(K_{2, 3, n}\), J. Graph Theory, 10, 1, 1-8 (1986) · Zbl 0586.05014 |
| [8] | Auer, C.; Bachmaier, C.; Brandenburg, F. J.; Gleißner, A.; Hanauer, K.; Neuwirth, D.; Reislhuber, J., Recognizing outer 1-planar graphs in linear time, (GD. GD, LNCS, vol. 8242 (2013)), 107-118 · Zbl 1406.68057 |
| [9] | Auer, C.; Brandenburg, F.-J.; Gleißner, A.; Hanauer, K., On sparse maximal 2-planar graphs, (GD. GD, LNCS, vol. 7704 (2012)), 555-556 |
| [10] | Bekos, M. A.; Cornelsen, S.; Grilli, L.; Hong, S.; Kaufmann, M., On the recognition of fan-planar and maximal outer-fan-planar graphs, (Graph Drawing. Graph Drawing, GD’14. Graph Drawing. Graph Drawing, GD’14, LNCS, vol. 8871 (2014), Springer), 198-209 · Zbl 1426.68200 |
| [11] | Bekos, M. A.; Cornelsen, S.; Grilli, L.; Hong, S.; Kaufmann, M., On the recognition of fan-planar and maximal outer-fan-planar graphs (2014), CoRR · Zbl 1426.68200 |
| [12] | Binucci, C.; Di Giacomo, E.; Didimo, W.; Montecchiani, F.; Patrignani, M.; Tollis, I. G., Fan-planar graphs: combinatorial properties and complexity results, (Graph Drawing. Graph Drawing, GD’14. Graph Drawing. Graph Drawing, GD’14, LNCS, vol. 8871 (2014), Springer), 186-197 · Zbl 1427.68231 |
| [13] | Binucci, C.; Di Giacomo, E.; Didimo, W.; Montecchiani, F.; Patrignani, M.; Tollis, I. G., Properties and complexity of fan-planarity (2014), CoRR |
| [14] | Bodendiek, R.; Schumacher, H.; Wagner, K., Über 1-optimale graphen, Math. Nachr., 117, 323-339 (1984) · Zbl 0558.05017 |
| [15] | Brandenburg, F.-J.; Eppstein, D.; Gleißner, A.; Goodrich, M. T.; Hanauer, K.; Reislhuber, J., On the density of maximal 1-planar graphs, (GD. GD, LNCS, vol. 7704 (2012)), 327-338 · Zbl 1377.68165 |
| [16] | Cheong, O.; Har-Peled, S.; Kim, H.; Kim, H.-S., On the number of edges of fan-crossing free graphs, (ISAAC. ISAAC, LNCS, vol. 8283 (2013)), 163-173 · Zbl 1329.05079 |
| [17] | Czap, J.; Hudák, D., 1-Planarity of complete multipartite graphs, Discrete Appl. Math., 160, 4-5, 505-512 (2012) · Zbl 1239.05039 |
| [18] | Dehkordi, H. R.; Eades, P., Every outer-1-plane graph has a right angle crossing drawing, Internat. J. Comput. Geom. Appl., 22, 6, 543-558 (2012) · Zbl 1267.68165 |
| [19] | Di Giacomo, E.; Didimo, W.; Eades, P.; Liotta, G., 2-Layer right angle crossing drawings, Algorithmica, 68, 4, 954-997 (2014) · Zbl 1303.05129 |
| [20] | Di Giacomo, E.; Didimo, W.; Liotta, G.; Meijer, H., Area, curve complexity, and crossing resolution of non-planar graph drawings, Theory Comput. Syst., 49, 3, 565-575 (2011) · Zbl 1252.68210 |
| [21] | Di Giacomo, E.; Didimo, W.; Liotta, G.; Montecchiani, F., \(h\)-quasi planar drawings of bounded treewidth graphs in linear area, (WG. WG, LNCS, vol. 7551 (2012)), 91-102 · Zbl 1341.05173 |
| [22] | 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 |
| [23] | Dickerson, M.; Eppstein, D.; Goodrich, M. T.; Meng, J. Y., Confluent drawings: visualizing non-planar diagrams in a planar way, J. Graph Algorithms Appl., 9, 1, 31-52 (2005) · Zbl 1086.05022 |
| [24] | Didimo, W., Density of straight-line 1-planar graph drawings, Inform. Process. Lett., 113, 7, 236-240 (2013) · Zbl 1259.05107 |
| [25] | Didimo, W.; Eades, P.; Liotta, G., Drawing graphs with right angle crossings, Theoret. Comput. Sci., 412, 39, 5156-5166 (2011) · Zbl 1225.68134 |
| [26] | Didimo, W.; Liotta, G., The crossing angle resolution in graph drawing, (Pach, J., Thirty Essays on Geometric Graph Theory (2012), Springer) · Zbl 1272.05128 |
| [27] | Dujmović, V.; Gudmundsson, J.; Morin, P.; Wolle, T., Notes on large angle crossing graphs, Chic. J. Theoret. Comput. Sci., 2011 (2011) · Zbl 1286.05034 |
| [28] | Eades, P.; Liotta, G., Right angle crossing graphs and 1-planarity, Discrete Appl. Math., 161, 7-8, 961-969 (2013) · Zbl 1408.05042 |
| [29] | Eppstein, D.; Goodrich, M. T.; Meng, J. Y., Confluent layered drawings, Algorithmica, 47, 4, 439-452 (2007) · Zbl 1118.68103 |
| [30] | 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 |
| [31] | Garey, M. R.; Johnson, D. S., Crossing number is NP-complete, SIAM J. Algebr. Discrete Methods, 4, 3, 312-316 (1983) · Zbl 0536.05016 |
| [32] | Grigoriev, A.; Bodlaender, H. L., Algorithms for graphs embeddable with few crossings per edge, Algorithmica, 49, 1, 1-11 (2007) · Zbl 1131.68120 |
| [33] | Hong, S.-H.; Eades, P.; Katoh, N.; Liotta, G.; Schweitzer, P.; Suzuki, Y., A linear-time algorithm for testing outer-1-planarity, (GD. GD, LNCS, vol. 8242 (2013)), 71-82 · Zbl 1406.68083 |
| [34] | Hong, S.-H.; Eades, P.; Liotta, G.; Poon, S.-H., Fáry’s theorem for 1-planar graphs, (COCOON. COCOON, LNCS, vol. 7434 (2012)), 335-346 · Zbl 1364.68308 |
| [35] | Kaufmann, M.; Ueckerdt, T., The density of fan-planar graphs (2014), CoRR |
| [36] | 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 |
| [37] | Pach, J.; Tóth, G., Graphs drawn with few crossings per edge, Combinatorica, 17, 3, 427-439 (1997) · Zbl 0902.05017 |
| [38] | Schaefer, M., The graph crossing number and its variants: a survey, Electron. J. Combin., 20, 2 (2013) · Zbl 1267.05180 |
| [39] | Suzuki, Y., Optimal 1-planar graphs which triangulate other surfaces, Discrete Math., 310, 1, 6-11 (2010) · Zbl 1188.05056 |
| [40] | Suzuki, Y., Re-embeddings of maximum 1-planar graphs, SIAM J. Discrete Math., 24, 4, 1527-1540 (2010) · Zbl 1221.05099 |
| [41] | 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.
