|
|||||
|
|
Minimal Obstructions for 1‐Immersions and Hardness of 1‐Planarity Testing |
|
| Authors: | Vladimir P Korzhik Bojan Mohar |
| Institution: | 1. NATIONAL UNIVERSITY OF CHERNIVTSI CHERNIVTSI UKRAINE AND INSTITUTE OF APPLIED PROBLEMS OF MECHANICS AND MATHEMATICS OF NATIONAL ACADEMY OF SCIENCE OF UKRAINE, , LVIV, UKRAINEThis paper was done while the author visited Simon Fraser University.;2. DEPARTMENT OF MATHEMATICS, SIMON FRASER UNIVERSITY, , BURNABY, B.C. V5A 1S6 CANADAContract grant sponsors: ARRS (Slovenia);3. NSERC Discovery Grant (Canada);4. Canada Research Chair program;5. Contract grant number: P1–0297.On leave from IMFM, and FMF, Department of Mathematics, University of Ljubljana, Ljubljana, Slovenia. |
| Abstract: | 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  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  , there are at least  nonisomorphic minimal non‐1‐planar graphs of order n. It is also proved that testing 1‐planarity is NP‐complete. |
| Keywords: | topological graph crossing edges 1‐planar graph 1‐immersion |