Characterizing 5-map graphs by 2-fan-crossing graphs. (English) Zbl 1419.05142
Summary: A map is a partition of the sphere or the plane into regions that are labeled as countries or holes. A graph is a \(k\)-map graph if the vertices correspond to the countries so that at most \(k\) countries meet in a point and there is an edge if and only if the corresponding countries are adjacent and share at least a point on their boundaries. A graph is \(r\)-fan-crossing if it admits a drawing in the plane so that each edge is crossed by at most \(r\) edges that are incident to a common vertex and form a fan.
We characterize the 5-map graphs as the clique-augmented 2-fan-crossing graphs. These admit 2-fan-crossing drawings so that single edge crossings induce 4-cliques and 2-fan-crossings induce 5-cliques. Then we enumerate all 2-fan-crossing embeddings of \(K_6\) and \(K_7\) and present graphs with a unique 2-fan-crossing embedding. We show that an 8-clique minus two edges is 2-fan-crossing, whereas \(K_8 - e\) is not a 2-fan-crossing graph. The density of 5-map graphs is \(5 n - 10\), but there are maximal \(n\)-vertex 2-fan-crossing graphs with only \(3 . 125 n - 6 . 25\) edges. Finally, we show that there are 3-fan-crossing graphs with less than \(5 n - 10\) edges that are not 2-fan-crossing, and 6-map graphs that have no 5-map.
We characterize the 5-map graphs as the clique-augmented 2-fan-crossing graphs. These admit 2-fan-crossing drawings so that single edge crossings induce 4-cliques and 2-fan-crossings induce 5-cliques. Then we enumerate all 2-fan-crossing embeddings of \(K_6\) and \(K_7\) and present graphs with a unique 2-fan-crossing embedding. We show that an 8-clique minus two edges is 2-fan-crossing, whereas \(K_8 - e\) is not a 2-fan-crossing graph. The density of 5-map graphs is \(5 n - 10\), but there are maximal \(n\)-vertex 2-fan-crossing graphs with only \(3 . 125 n - 6 . 25\) edges. Finally, we show that there are 3-fan-crossing graphs with less than \(5 n - 10\) edges that are not 2-fan-crossing, and 6-map graphs that have no 5-map.
MSC:
| 05C62 | Graph representations (geometric and intersection representations, etc.) |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
References:
| [1] | Alam, M. J.; Brandenburg, F. J.; Kobourov, S. G., Straight-line drawings of 3-connected 1-planar graphs, (Wismath, S.; Wolff, A., Proc. 21st GD 2013. Proc. 21st GD 2013, LNCS, vol. 8242 (2013), Springer), 83-94 · Zbl 1406.68054 |
| [2] | 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 |
| [3] | Bachmaier, C.; Brandenburg, F. J.; Hanauer, K.; Neuwirth, D.; Reislhuber, J., Nic-planar graphs, Discrete Appl. Math., 232, 23-40 (2017) · Zbl 1372.05047 |
| [4] | Bekos, M. A.; Cornelsen, S.; Grilli, L.; Hong, S.; Kaufmann, M., On the recognition of fan-planar and maximal outer-fan-planar graphs, Algorithmica, 79, 2, 401-427 (2017) · Zbl 1372.68201 |
| [5] | 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 |
| [6] | Bodendiek, R.; Schumacher, H.; Wagner, K., Bemerkungen zu einem Sechsfarbenproblem von G. Ringel, Abh. Math. Semin. Univ. Hambg., 53, 41-52 (1983) · Zbl 0495.05020 |
| [7] | Bodendiek, R.; Schumacher, H.; Wagner, K., Über 1-optimale Graphen, Math. Nachr., 117, 323-339 (1984) · Zbl 0558.05017 |
| [8] | Brandenburg, F. J., On fan-crossing graphs (2017), CoRR, abs/171206840 · Zbl 1461.68145 |
| [9] | Brandenburg, F. J., A first order logic definition of beyond-planar graphs, J. Graph Algorithms Appl., 22, 1, 51-66 (2018) · Zbl 1377.05120 |
| [10] | Brandenburg, F. J., Characterizing and recognizing 4-map graphs, Algorithmica, 81, 5, 1818-1843 (2019) · Zbl 1423.05050 |
| [11] | Brandenburg, F. J.; Didimo, W.; Evans, W. S.; Kindermann, P.; Liotta, G.; Montecchianti, F., Recognizing and drawing IC-planar graphs, Theoret. Comput. Sci., 636, 1-16 (2016) · Zbl 1342.68251 |
| [12] | Brandenburg, F. J.; Eppstein, D.; Gleißner, A.; Goodrich, M. T.; Hanauer, K.; Reislhuber, J., On the density of maximal 1-planar graphs, (van Kreveld, M.; Speckmann, B., Proc. GD 2012. Proc. GD 2012, LNCS, vol. 7704 (2013), Springer), 327-338 · Zbl 1377.68165 |
| [13] | Chen, Z., Approximation algorithms for independent sets in map graphs, J. Algorithms, 41, 1, 20-40 (2001) · Zbl 1002.68111 |
| [14] | Z. Chen, M. Grigni, C.H. Papadimitriou, Planar map graphs, in: Proc. 30th STOC’98, 1998, pp. 514-523.; Z. Chen, M. Grigni, C.H. Papadimitriou, Planar map graphs, in: Proc. 30th STOC’98, 1998, pp. 514-523. · Zbl 1028.68104 |
| [15] | Chen, Z.; Grigni, M.; Papadimitriou, C. H., Map graphs, J. ACM, 49, 2, 127-138 (2002) · Zbl 1323.05039 |
| [16] | Chen, Z.; Grigni, M.; Papadimitriou, C. H., Recognizing hole-free 4-map graphs in cubic time, Algorithmica, 45, 2, 227-262 (2006) · Zbl 1095.68076 |
| [17] | Didimo, W.; Liotta, G.; Montecchiani, F., A survey on graph drawing beyond planarity, AMC Comput. Surv., 52, 1, 37 (2019), 4:1-4 |
| [18] | Diestel, R., Graph Theory (2000), Springer · Zbl 0945.05002 |
| [19] | Grigoriev, A.; Bodlaender, H. L., Algorithms for graphs embeddable with few crossings per edge, Algorithmica, 49, 1, 1-11 (2007) · Zbl 1131.68120 |
| [20] | Harborth, H.; Mengersen, I., Drawings of the complete graph with maximum number of crossings, Congr. Numer., 88, 225-228 (1992) · Zbl 0792.05043 |
| [21] | Kaufmann, M.; Ueckerdt, T., The density of fan-planar graphsTechnical Report (2014), Computing Research Repository (CoRR), arXiv:14036184 [cs.DM] |
| [22] | Kobourov, S. G.; Liotta, G.; Montecchiani, F., An annotated bibliography on 1-planarity, Comput. Sci. Rev., 25, 49-67 (2017) · Zbl 1398.68402 |
| [23] | Korzhik, V. P.; Mohar, B., Minimal obstructions for 1-immersion and hardness of 1-planarity testing, J. Graph Theory, 72, 30-71 (2013) · Zbl 1259.05046 |
| [24] | 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 |
| [25] | Pach, J.; Tóth, G., Graphs drawn with a few crossings per edge, Combinatorica, 17 (1997) · Zbl 0902.05017 |
| [26] | Ringel, G., Ein sechsfarbenproblem auf der kugel, Abh. Math. Semin. Univ. Hambg., 29, 107-117 (1965) · Zbl 0132.20701 |
| [27] | Schumacher, H., Zur Struktur 1-planarer Graphen, Math. Nachr., 125, 291-300 (1986) · Zbl 0594.05026 |
| [28] | Handbook of Graph Drawing and Visualization (2013), CRC Press |
| [29] | Thorup, M., Map graphs in polynomial time, (Proc. 39th FOCS (1998), IEEE Computer Society), 396-405 |
| [30] | Whitney, H., Planar graphs, Fund. Math., 21, 73-84 (1933) · JFM 59.1235.03 |
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.
