Drawing Complete Multipartite Graphs on the Plane with Restrictions on Crossings  

作　　者：Xin ZHANG 

机构地区：[1]School of Mathematics and Statistics,Xidian University

出　　处：《Acta Mathematica Sinica,English Series》2014年第12期2045-2053,共9页数学学报（英文版）

基　　金：Supported by National Natural Science Foundation of China(Grant Nos.11301410,11201440,11101243);the Natural Science Basic Research Plan in Shaanxi Province of China(Grant No.2013JQ1002);the Specialized Research Fund for the Doctoral Program of Higher Education(Grant No.20130203120021);the Fundamental Research Funds for the Central Universities(Grant Nos.K5051370003,K5051370021)

摘　　要：A graph is 1-planar if it can be drawn on a plane so that each edge is crossed by at most one other edge. A plane graph with near independent crossings （say NIC-planar graph） is a 1-planar graph with the restriction that for any two crossings the four crossed edges are incident with at most one common vertex. The full characterization of NIC-planar complete and complete multipartite graphs is given in this paper.A graph is 1-planar if it can be drawn on a plane so that each edge is crossed by at most one other edge. A plane graph with near independent crossings （say NIC-planar graph） is a 1-planar graph with the restriction that for any two crossings the four crossed edges are incident with at most one common vertex. The full characterization of NIC-planar complete and complete multipartite graphs is given in this paper.

关 键 词：1-Planar graph independent crossings crossing number 

分 类 号：O157.5[理学—数学] TH126[理学—基础数学]