On Drawings and Decompositions of 1-Planar Graphs

  • 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: 1-planar graph, planar graph, forest

Abstract

A graph is called 1-planar 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 1-planar drawing of any 1-planar graph on $n$ vertices has at most $n-2$ crossings; moreover, this bound is tight. By this novel necessary condition for 1-planarity, we characterize the 1-planarity 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 1-planar graphs, and we show that each subgraph of an optimal 1-planar graph (i.e., a 1-planar graph with $n$ vertices and $4n-8$ edges) can be decomposed into a planar graph and a forest.
Published
2013-06-13
Article Number
P54