Minimal obstructions for 1-immersions and hardness of 1-planarity testing

Details Minimal obstructions for 1-immersions and hardness of 1-planarity testing Minimal obstructions for 1-immersions and hardness of 1-planarity testing

2011-10-21

arxiv.org/abs/1110.4881v1

Mathematics

Combinatorics

55 pages

Scientific paper

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 > 62$, there are at least $2^{(n-54)/4}$ nonisomorphic minimal non-1-planar graphs of order $n$. It is also proved that testing 1-planarity is NP-complete.

Affiliated with

Also associated with

No associations

Rating

Minimal obstructions for 1-immersions and hardness of 1-planarity testing does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Minimal obstructions for 1-immersions and hardness of 1-planarity testing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Minimal obstructions for 1-immersions and hardness of 1-planarity testing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-85966