Drawing complete multipartite graphs on the plane with restrictions on crossings

DOI10.1007/S10114-014-3763-6zbMATH Open1304.05031arXiv1311.1994OpenAlexW2133295546MaRDI QIDQ477904FDOQ477904

Authors: Xin Zhang 

Publication date: 10 December 2014

Published in: Acta Mathematica Sinica, English Series (Search for Journal in Brave)

Abstract: We introduce the concept of NIC-planar graphs and present the full characterization of NIC-planar complete k-partite graphs.

Full work available at URL: https://arxiv.org/abs/1311.1994

Recommendations

• 1-planarity of complete multipartite graphs
• New results on edge partitions of 1-plane graphs
• \(\mathsf{NIC}\)-planar graphs
• The coloring of the class of 1-planar graphs and its subclasses
• On drawings and decompositions of 1-planar graphs

zbMATH Keywords

crossing number1-planar graphindependent crossings

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Graph theory
• A new proof of the 6 color theorem
• Reduction of symmetric semidefinite programs using the regular \(\ast\)-representation
• Ein Sechsfarbenproblem auf der Kugel
• The structure of plane graphs with independent crossings and its applications to coloring problems
• Coloring plane graphs with independent crossings
• Title not available (Why is that?)
• 1-planarity of complete multipartite graphs
• The crossing number of \(K_{1,4,n}\)
• The crossing number of K5,n
• Title not available (Why is that?)
• On \((p,1)\)-total labelling of plane graphs with independent crossings
• On the crossing number of some complete multipartite graphs
• The crossing number ofK1,3,n andK2,3,n

Cited In (24)

• 1-planarity of complete multipartite graphs
• Weak-dynamic coloring of graphs beyond-planarity
• Recognizing IC-planar and NIC-planar graphs
• Neighbor sum distinguishing total choice number of NIC-planar graphs with restricted conditions
• On \((p, 1)\)-total labelling of NIC-planar graphs
• Equitable coloring of three classes of 1-planar graphs
• Linear arboricity of NIC-planar graphs
• Efficient generation of different topological representations of graphs beyond-planarity
• On the sizes of bipartite 1-planar graphs
• The coloring of the class of 1-planar graphs and its subclasses
• Equitable partition of plane graphs with independent crossings into induced forests
• Title not available (Why is that?)
• The structure and the bondage number of three classes of beyond-planar graphs
• \(\mathsf{NIC}\)-planar graphs
• Remarks on the joins of 1-planar graphs
• Strong Edge Coloring of Outerplane Graphs with Independent Crossings
• Total coloring of outer-1-planar graphs with near-independent crossings
• An annotated bibliography on 1-planarity
• The surviving rate of NIC-planar graphs
• New results on edge partitions of 1-plane graphs
• IC-planar graphs are 6-choosable
• Beyond-planarity: Turán-type results for non-planar bipartite graphs
• On optimal beyond-planar graphs
• Drawing graph joins in the plane with restrictions on crossings

This page was built for publication: Drawing complete multipartite graphs on the plane with restrictions on crossings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q477904)