Joins of 1-planar graphs

DOI10.1007/S10114-014-4017-3MaRDI QIDQ477875zbMATH OpenOpenAlexFDO

Authors Július Czap, Tomáš Madaras, Dávid Hudák

Publication date 10 December 2014

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

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

zbMATH Keywords

1-planar graphjoin product

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: A graph is called 1-planar if there exists its drawing in the plane such that each edge is crossed at most once. In this paper, we study 1-planar graph joins. We prove that the join $G+H$ is 1-planar if and only if the pair $[G,H]$ is subgraph-majorized (that is, both $G$ and $H$ are subgraphs of graphs of the major pair) by one of pairs $[C_{3}cup{C}_3,C_3],[C_4,C_4],[C_4,C_3],[K_{2,1,1},P_3]$ in the case when both factors of the graph join have at least three vertices. If one factor has at most two vertices, then we give several necessary/sufficient conditions for the bigger factor.

Recommendations

• Drawing graph joins in the plane with restrictions on crossings
• Remarks on the joins of 1-planar graphs
• Planarity of joined graphs
• 1-planarity of complete multipartite graphs
• The structure of 1-planar graphs

Cites work

• scientific article; zbMATH DE number 6506585 (Why is no real title available?)
• scientific article; zbMATH DE number 3924797 (Why is no real title available?)
• 1-planarity of complete multipartite graphs
• Characterization of join graphs with crossing number zero
• Ein Sechsfarbenproblem auf der Kugel
• Fáry's theorem for 1-planar graphs
• Graph theory
• Graphs drawn with few crossings per edge
• On Topological Invariants of the Product of Graphs
• The Join of Graphs and Crossing Numbers
• The crossing number of K5,n
• The crossing numbers of join of the special graph on six vertices with path and cycle
• The crossing numbers of join products of paths with graphs of order four
• The structure of 1-planar graphs

Cited in

(7)

• Planarity of joined graphs
• 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
• Remarks on the joins of 1-planar graphs
• An annotated bibliography on 1-planarity
• Drawing graph joins in the plane with restrictions on crossings

This page was built for publication: Joins of 1-planar graphs

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