Planar crossing numbers of graphs of bounded genus. (English) Zbl 1248.05044
Summary: J. Pach and G. Tóth [Algorithms and Combinatorics 26, 581–590 (2006; Zbl 1117.05032)] proved that any \(n\)-vertex graph of genus \(g\) and maximum degree \(d\) has a planar crossing number at most \(c ^{g } dn\), for a constant \(c>1\). We improve on this result by decreasing the bound to \(O(dgn)\), and also prove that our result is tight within a constant factor. Our proof is constructive and yields an algorithm with time complexity \(O(dgn)\). As a consequence of our main result, we show a relation between the planar crossing number and the surface crossing number.
MSC:
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 57M15 | Relations of low-dimensional topology with graph theory |
Citations:
Zbl 1117.05032References:
| [1] | Ajtai, M., Chvátal, V., Newborn, M.M., Szemerédi, E.: Crossing-free subgraphs. Ann. Discrete Math. 12, 9-12 (1982) · Zbl 0502.05021 |
| [2] | Börözky, K.J., Pach, J., Tóth, G.: Planar crossing numbers of graphs embeddable in another surface. Int. J. Found. Comput. Sci. 17(5), 1005-1016 (2006) · Zbl 1100.68075 · doi:10.1142/S0129054106004236 |
| [3] | Chimani, M.; Mutzel, P.; Bomze, I., A new approach to exact crossing minimization, 284-296 (2008), Berlin · Zbl 1158.90423 |
| [4] | Chuzhoy, J.; Fortnow, L. (ed.); Vadhan, S. P. (ed.), An algorithm for the graph crossing number problem, 303-312 (2011), New York · Zbl 1288.68259 |
| [5] | Cimikowski, R.: Algorithms for the fixed linear crossing number problem. Discrete Appl. Math. 122, 93-115 (2002) · Zbl 1002.68194 · doi:10.1016/S0166-218X(01)00314-6 |
| [6] | Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for Visualization of Graphs. Prentice Hall, New York (1999) · Zbl 1057.68653 |
| [7] | Djidjev, H., Vrto, I.: Crossing numbers and cutwidths. J. Graph Algorithms Appl. 7(3), 245-251 (2003) · Zbl 1066.05054 |
| [8] | Djidjev, H.N.: Partitioning planar graphs with vertex costs: algorithms and applications. Algorithmica 28(1), 51-75 (2000) · Zbl 0959.68098 · doi:10.1007/s004530010031 |
| [9] | Even, G., Guha, S., Schieber, B.: Improved approximations of crossings in graph drawings and VLSI layout areas. SIAM J. Comput. 32(1), 231-252 (2002) · Zbl 1029.68160 · doi:10.1137/S0097539700373520 |
| [10] | Garey, R., Johnson, D.S.: Crossing number is NP-complete. SIAM J. Algebr. Discrete Methods 4, 312-316 (1983) · Zbl 0536.05016 · doi:10.1137/0604033 |
| [11] | Glebsky, L.Y., Salazar, G.: The crossing number of cr(cm×cn) is as conjectured for n≥m(m+1). J. Graph Theory 47, 53-72 (2004) · Zbl 1053.05032 · doi:10.1002/jgt.20016 |
| [12] | Grohe, M.: Computing crossing numbers in quadratic time. J. Comput. Syst. Sci. 68(2), 285-302 (2004) · Zbl 1073.68064 · doi:10.1016/j.jcss.2003.07.008 |
| [13] | Hliněný, P.: Crossing number is hard for cubic graphs. J. Comb. Theory, Ser. B 96, 455-471 (2006) · Zbl 1092.05016 · doi:10.1016/j.jctb.2005.09.009 |
| [14] | Kawarabayashi, K.i.; Reed, B., Computing crossing number in linear time, 382-390 (2007), New York · Zbl 1232.90339 |
| [15] | Leighton, F.T.: Complexity Issues in VLSI. MIT Press, Cambridge (1983) |
| [16] | Liebers, A.: Methods for planarizing graphs—a survey and annotated bibliography. J. Graph Algorithms Appl. 5, 1-74 (2001) · Zbl 0966.05022 |
| [17] | Pach, J., Radoicic, R., Tardos, G., Toth, G.: Improving the crossing lemma by finding more crossings in sparse graphs. Discrete Comput. Geom. 36, 527-552 (2006) · Zbl 1104.05022 · doi:10.1007/s00454-006-1264-9 |
| [18] | Pach, J., Shahrokhi, F., Szegedy, M.: Applications of the crossing number. Algorithmica 16, 111-117 (1996) · Zbl 0851.68088 · doi:10.1007/BF02086610 |
| [19] | Pach, J.; Tóth, G.; Klazar, M. (ed.); etal., Crossing number of toroidal graphs, No. 3843, 334-342 (2006), Berlin · Zbl 1171.05326 · doi:10.1007/11618058_30 |
| [20] | Shahrokhi, F.; Sýkora, O.; Székely, L.; Vrt’o, I., Crossing numbers: bounds and applications, 179-206 (1997), Budapest · Zbl 0890.05022 |
| [21] | Sýkora, O., Vrt’o, I.: Edge separators for graphs of bounded genus with applications. Theor. Comput. Sci. 112, 419-429 (1993) · Zbl 0772.05057 · doi:10.1016/0304-3975(93)90031-N |
| [22] | Sýkora, O., Vrt’o, I.: Optimal VLSI layouts of the star graph and related networks. Integration 17, 83-94 (1994) · Zbl 0813.94026 |
| [23] | Vrt’o, I.: Crossing numbers of graphs: a bibliography. Available electronically at http://www.ifi.savba.sk/ imrich · Zbl 1223.05038 |
| [24] | Wood, D. R.; Telle, J. A., Planar decompositions and the crossing number of graphs with an excluded minor, 150-161 (2007), Berlin · Zbl 1185.05050 |
| [25] | Yuan-qui, H., Jing, W.: Survey of the crossing number of graphs. J. East China Norm. Univ. Natur. Sci. Ed. 3, 68-80 (2010) · Zbl 1240.05220 |
| [26] | Zarankiewicz, K.: On a problem of P. Turán concerning graphs. Fundam. Math. 41, 137-145 (1954) · Zbl 0055.41605 |
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.
