Premium
Minimal Obstructions for 1‐Immersions and Hardness of 1‐Planarity Testing
Author(s) -
Korzhik Vladimir P.,
Mohar Bojan
Publication year - 2013
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21630
Subject(s) - planarity testing , combinatorics , mathematics , planar graph , planar , outerplanar graph , book embedding , graph , planar straight line graph , discrete mathematics , enhanced data rates for gsm evolution , 1 planar graph , pathwidth , line graph , computer science , telecommunications , computer graphics (images)
A graph is 1‐ planar if it can be drawn on the plane so that each edge is crossed by no more than one other edge (and any pair of crossing edges cross only once). A non‐1‐planar graph G is minimal if the graph G − e is 1‐planar for every edge e of G . We construct two infinite families of minimal non‐1‐planar graphs and show that for every integer n ≥ 63 , there are at least 2 ( n − 54 ) / 4nonisomorphic minimal non‐1‐planar graphs of order n . It is also proved that testing 1‐planarity is NP‐complete.