Joins of 1-planar graphs
Július Czap, Dávid Hudák, Tomáš Madaras · 2016
A graph is called 1-planar if it admits a 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 by one of pairs [C 3 ∪ C 3, C 3], [C 4, C 4], [C 4,C 3], [K 2,1,1, P 3] in the case when both elements of the graph join have at least three vertices. If one element has at most two vertices, then we give several necessary/sufficient conditions for the bigger element.