1Department of Applied Mathematics and Business Informatics, Faculty of Economics, Technical University of Košice 2Institute of Mathematics, Faculty of Science, Pavol Jozef Šafárik University
The electronic journal of combinatorics, Tome 20 (2013) no. 2
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.
1
Department of Applied Mathematics and Business Informatics, Faculty of Economics, Technical University of Košice
2
Institute of Mathematics, Faculty of Science, Pavol Jozef Šafárik University
@article{10_37236_2392,
author = {J\'ulius Czap and D\'avid Hud\'ak},
title = {On drawings and decompositions of 1-planar graphs},
journal = {The electronic journal of combinatorics},
year = {2013},
volume = {20},
number = {2},
doi = {10.37236/2392},
zbl = {1295.05084},
url = {http://geodesic.mathdoc.fr/articles/10.37236/2392/}
}
TY - JOUR
AU - Július Czap
AU - Dávid Hudák
TI - On drawings and decompositions of 1-planar graphs
JO - The electronic journal of combinatorics
PY - 2013
VL - 20
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/2392/
DO - 10.37236/2392
ID - 10_37236_2392
ER -
%0 Journal Article
%A Július Czap
%A Dávid Hudák
%T On drawings and decompositions of 1-planar graphs
%J The electronic journal of combinatorics
%D 2013
%V 20
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/2392/
%R 10.37236/2392
%F 10_37236_2392
Július Czap; Dávid Hudák. On drawings and decompositions of 1-planar graphs. The electronic journal of combinatorics, Tome 20 (2013) no. 2. doi: 10.37236/2392
