
Július Czap
Department of Applied Mathematics and Business Informatics, Faculty of Economics, Technical University of Košice

Dávid Hudák
Institute of Mathematics, Faculty of Science, Pavol Jozef Šafárik University
Keywords:
1planar graph, planar graph, forest
Abstract
A graph is called 1planar if it can be drawn in the plane so that each of its edges is crossed by at most one other edge. We show that every 1planar drawing of any 1planar graph on $n$ vertices has at most $n2$ crossings; moreover, this bound is tight. By this novel necessary condition for 1planarity, we characterize the 1planarity of Cartesian product $K_m\times P_n$. Based on this condition, we also derive an upper bound on the number of edges of bipartite 1planar graphs, and we show that each subgraph of an optimal 1planar graph (i.e., a 1planar graph with $n$ vertices and $4n8$ edges) can be decomposed into a planar graph and a forest.