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.
展开▼
