1-planarity of complete multipartite graphs

DOI10.1016/j.dam.2011.11.014zbMath1239.05039OpenAlexW2080939450MaRDI QIDQ412349

Július Czap, David E. Hudak

Publication date: 4 May 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2011.11.014

zbMATH Keywords

1-planar graphcomplete \(k\)-partite graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (25)

On the Size of Matchings in 1-Planar Graph with High Minimum Degree ⋮ Packing Trees into 1-planar Graphs ⋮ On quasi-planar graphs: clique-width and logical description ⋮ Generalized cut and metric polytopes of graphs and simplicial complexes ⋮ An annotated bibliography on 1-planarity ⋮ On drawings and decompositions of 1-planar graphs ⋮ A note on 1-planar graphs ⋮ k-Planar Placement and Packing of Δ-Regular Caterpillars ⋮ Maximal 1-plane graphs with dominating vertices ⋮ On an extremal problem in the class of bipartite 1-planar graphs ⋮ Right angle crossing graphs and 1-planarity ⋮ Efficient generation of different topological representations of graphs beyond-planarity ⋮ An upper bound on the sum of powers of the degrees of simple 1-planar graphs ⋮ Joins of 1-planar graphs ⋮ Drawing complete multipartite graphs on the plane with restrictions on crossings ⋮ Efficient Generation of Different Topological Representations of Graphs Beyond-Planarity ⋮ Light edges in 3-connected 2-planar graphs with prescribed minimum degree ⋮ On the sizes of bipartite 1-planar graphs ⋮ 1-embeddability of complete multipartite graphs on the projective plane ⋮ Non-1-planarity of lexicographic products of graphs ⋮ Unnamed Item ⋮ 1-Planar Graphs ⋮ Drawing graph joins in the plane with restrictions on crossings ⋮ From light edges to strong edge-colouring of 1-planar graphs ⋮ Fan-planarity: properties and complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Ein 7-Farbensatz 1-einbettbarer Graphen auf der projektiven Ebene
• A linear-time algorithm for 7-coloring 1-plane graphs
• The structure of 1-planar graphs
• Graphs drawn with few crossings per edge
• Ein Sechsfarbenproblem auf der Kugel
• Minimal non-1-planar graphs
• The crossing number of \(K_{1,4,n}\)
• Minimal Obstructions for 1-Immersions and Hardness of 1-Planarity Testing
• Efficient Planarity Testing
• A new proof of the 6 color theorem
• The crossing number of K5,n

This page was built for publication: 1-planarity of complete multipartite graphs