2-可平面图的交叉数及其应用
The Crossing Number of 2-planar Graphs and Its Application
图在平面内具有最小交叉次数的嵌入称为该图的一个最优平面画法.图G的交叉数cr(G)是该图的最优平面画法中的交叉次数.如果一个图可以嵌入在平面内使得每条边最多被交叉k次,则称其为k-可平面图.Zhang等人(2012)证明了顶点数为n的1-可平面图的交叉数最多为n-2,并且该上界是最优的.Czap,Harant与Hudák(2014)证明了顶点数为n的2-可平面图的交叉数最多为5(n-2).本文给出了2-可平面图的交叉数的一个更好的上界,并利用它从组合学的角度证明了Kn是2-可平面图当且仅当n ≤ 7(该问题于2019年之前是个公开问题,最近由Angelini等人使用计算机程序证明).
An optimal planar drawing of a graph is an embedding in the plane so that the number of crossings is as small as possible. The number of crossings in an optimal planar drawing of a graph G is the crossing number cr(G) of G. A graph is k-planar if it can be embedded in the planar so that each edge is crossed at most k times. Zhang et al. (2012) proved that the crossing number of any 1-planar graph on n vertices is at most n -2, and this upper bound is best possible. Czap, Harant and Hudák (2014) proved that the crossing number of any 2-planar graph on n vertices is at most 5(n-2). In this paper, we give a better upper bound for the crossing number of 2-planar graphs and show from the point of view of combinatorics that Kn is 2-planar if and only if n ≤ 7 (surprisedly, this was an open problem until 2019, in when Angelini solved it with computer assistance).
2-平面图 / 交叉数 / 权转移方法 / 完全图 {{custom_keyword}} /
2-planar graph / crossing number / discharging method / complete graph {{custom_keyword}} /
[1] Angelini P., Bekos M. A., Kaufmann M., et al., Efficient generation of different topological representations of graphs beyond-planarity, In:C. D. Tóth and D. Archambault eds., Proc. of 27th International Symposium on Graph Drawing (GD 2019), 2019.
[2] Auer C., Brandenburg F., Gleiβner A., et al., On sparse maximal 2-planar graphs, In:Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), LNCS 7704, 2013:555-556.
[3] Bekos M., Di Giacomo E., Didimo W., et al., Edge partitions of optimal 2-plane and 3-plane graphs, Discrete Mathematics, 2019, 342(4):1038-1047.
[4] Cabello S., Mohar B., Adding one edge to planar graphs makes crossing number and 1-planarity hard, SIAM Journal on Computing, 2013, 42(5):1803-1829.
[5] Chimani M., Kindermann P., Montecchiani F., et al., Crossing numbers of beyond-planar graphs, In:Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), LNCS 11904, 2019:78-86.
[6] Czap J., Harant J., Hudák D., An upper bound on the sum of powers of the degrees of simple 1-planar graphs, Discrete Applied Mathematics, 2014, 165:146-151.
[7] Didimo W., Liotta G., Montecchiani F., A survey on graph drawing beyond planarity, ACM Computing Surveys, 2019, 52(1):Art. No4, 37pp.
[8] Diestel R., Graph Theory (5th Edition), Springer, Berlin, 2017.
[9] Garey M. R., Johnson D. S., Crossing number is NP-complete, SIAM Journal on Algebraic Discrete Methods, 1983, 4(3):312-316.
[10] Guy R. K., A combinatorial problem, Nabla (Bulletin of the Malayan Mathematical Society), 1960, 7:68-72.
[11] Guy R. K., Crossing numbers of graphs, In:Graph Theory and Applications (Y. Alavi, D. R. Lick, and A. T. White, Eds.), Springer, Berlin, Heidelberg, 1972:111-124.
[12] Hliněný P., Crossing number is hard for cubic graphs, Journal of Combinatorial Theory, Series B, 2006, 96(4):455-471.
[13] Hoffmann M., Tóth C., Two-planar graphs are quasiplanar, In:42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017), Francois Raskin, 2017, Art. No47:1-14.
[14] Kobourov S., Liotta G., Montecchiani F., An annotated bibliography on 1-planarity, Computer Science Review, 2017, 25:49-67.
[15] Leighton T., Complexity Issues in VLSI, Foundations of Computing Series, MIT Press, Cambridge, 1983.
[16] Lu Z., Song N., Light edges in 3-connected 2-planar graphs with prescribed minimum degree, Bulletin of the Malaysian Mathematical Sciences Society, 2018, 41(3):1265-1274.
[17] Pach J., Tóth G., Graphs drawn with few crossings per edge, Combinatorica, 1997, 17(3):427-439.
[18] Pan S., Richter R., The crossing number of K11 is 100, Journal of Graph Theory, 2007, 56(2):128-134.
[19] Saaty T. L., The minimum number of intersections in complete graphs, Proceedings of the National Academy of Sciences, 1964, 3:688-690.
[20] Schaefer M., The graph crossing number and its variants:A survey, Electronic Journal of Combinatorics, 2018, 1.
[21] Székely L., Crossing numbers and hard Erdös problems in discrete geometry. Combinatorics Probability and Computing, 1997, 6(3):353-358.
[22] Turán P., A note of welcome. Journal of Graph Theory, 1977, 1(1):7-9.
[23] Xu J., Graph Theory and Its Application (in Chinese), Press of University of Science and Technology of China, Hefei, 2019.
[24] Zhang X., Liu G., Wu J. L., (1, λ)-embedded graphs and the acyclic edge choosability. Bulletin of the Korean Mathematical Society, 2012, 49(3):573-580.
[25] Zhang X., Liu G., Wu J. L., Structural properties of 1-planar graphs and an application to acyclic edge coloring (in Chinese). Sci. Sin. Math., 2010, 40(10):1025-1032.
[26] Zhang X., Liu W., The coloring of the class of 1-planar graphs and its subclasses (in Chinese), Operations Research Transactions, 2017, 21(4):135-152.
国家自然科学基金资助项目(11871055);西安市科协青年人才托举计划资助项目(2018-6);国家留学基金委公派留学(访问学者)项目(201906965003)
/
〈 | 〉 |