I have a new preprint out with Michael Bannister and Sergio Cabello, "Parameterized complexity of 1-planarity", arXiv:1304.5591, to appear at WADS.

A graph is 1-planar if it can be drawn in the plane with at most one crossing per edge; the hope is that this style of drawing can be more versatile than completely forbidding crossings while still being constrained enough to keep the drawings readable. However, finding a 1-planar drawing is NP-hard. Our goal in this paper was to explore restrictions on input graphs that might make the problem easier, focusing on parameterized analysis rather than on special classes of graphs. We found some parameters that, when bounded, allow the problem to be solved by a polynomial time algorithm (with a small polynomial exponent but huge constant factors): vertex cover number, tree-depth, and circuit rank. The main idea for these algorithms is to reduce the input to a kernel whose size is bounded by a function of the parameter, before switching to a brute force algorithm. For instance, the kernelization for vertex cover number involves eliminating degree-one vertices and reducing the size of sets of degree-two vertices that all have the same two neighbors:

Kernelization for testing 1-planarity on graphs with bounded vertex cover number

A more commonly seen parameter for this sort of problem is treewidth. Many problems (and several important general families of problems) are known to be polynomial for graphs of bounded treewidth, but 1-planarity turns out not to be one of them. As we show the problem remains NP-complete in this case, as well as for graphs of bounded pathwidth and bounded bandwidth. The proof is just a standard gadget-based reduction, but not an easy one, and unfortunately we won't have space to include it in the conference version of the paper. One of the key ideas is the following construction, which (using some additional gadgets) forces a graph of bounded pathwidth to be drawn in a spiral pattern, providing a grid-like substrate over which the rest of the reduction can be forced to spread.

Low bandwidth double spiral, used as a substrate for an NP-completeness proof for testing 1-planarity of graphs of bounded bandwidth

There are still some interesting parameters as well as special classes of graphs for which we don't know whether 1-planarity is polynomial time. For instance, parameterizing by feedback vertex set size would generalize both our vertex cover and circuit rank results. We also don't know whether testing 1-planarity is polynomial for chordal graphs, or for distance-hereditary graphs.