2-可平面图的交叉数及其应用

删除或更新信息，请邮件至freekaoyan#163.com(#换成@)

本站小编 Free考研考试/2021-12-27

2-可平面图的交叉数及其应用张欣西安电子科技大学数学与统计学院西安 710071 The Crossing Number of 2-planar Graphs and Its Application Xin ZHANGSchool of Mathematics and Statistics, Xidian University, Xi'an 710071, P. R. China

摘要
图/表
参考文献
相关文章

全文: PDF(526 KB) HTML (1 KB)
输出: BibTeX | EndNote (RIS)

摘要图在平面内具有最小交叉次数的嵌入称为该图的一个最优平面画法.图G的交叉数cr（G）是该图的最优平面画法中的交叉次数.如果一个图可以嵌入在平面内使得每条边最多被交叉k次，则称其为k-可平面图.Zhang等人（2012）证明了顶点数为n的1-可平面图的交叉数最多为n-2，并且该上界是最优的.Czap，Harant与Hudák（2014）证明了顶点数为n的2-可平面图的交叉数最多为5（n-2）.本文给出了2-可平面图的交叉数的一个更好的上界，并利用它从组合学的角度证明了K_n是2-可平面图当且仅当n ≤ 7（该问题于2019年之前是个公开问题，最近由Angelini等人使用计算机程序证明）.

服务

加入引用管理器

E-mail Alert

RSS

收稿日期: 2020-01-20

MR (2010):

O157.5

基金资助:国家自然科学基金资助项目（11871055）；西安市科协青年人才托举计划资助项目（2018-6）；国家留学基金委公派留学（访问****）项目（201906965003）

作者简介: 张欣,E-mail:xzhang@xidian.edu.cn

引用本文:

张欣. 2-可平面图的交叉数及其应用[J]. 数学学报, 2021, 64(3): 463-470. Xin ZHANG. The Crossing Number of 2-planar Graphs and Its Application. Acta Mathematica Sinica, Chinese Series, 2021, 64(3): 463-470.

链接本文:

http://www.actamath.com/Jwk_sxxb_cn/CN/或 http://www.actamath.com/Jwk_sxxb_cn/CN/Y2021/V64/I3/463

[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 K₁₁ 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.

[1]	欧阳章东, 黄元秋. K_m□P_n的交叉数[J]. 数学学报, 2016, 59(3): 405-410.
[2]	尹建华. r-可图序列与r-完全子图[J]. Acta Mathematica Sinica, English Series, 2013, 56(3): 369-380.
[3]	李赵祥, 任韩. 不可定向曲面上的最大亏格嵌入和最小亏格嵌入[J]. Acta Mathematica Sinica, English Series, 2011, 54(2): 329-332.
[4]	徐俊明. 临界 h 棱连通图的最大棱数及其极值图[J]. Acta Mathematica Sinica, English Series, 1990, 33(6): 804-813.
[5]	刘振宏. 关于Win猜想的部分结果[J]. Acta Mathematica Sinica, English Series, 1987, 30(5): 675-678.

PDF全文下载地址:

http://www.actamath.com/Jwk_sxxb_cn/CN/article/downloadArticleFile.do?attachType=PDF&id=23763