摘要
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.
基金
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)
