Adding one edge to planar graphs makes crossing number and 1-planarity hard

Ein Sechsfarbenproblem auf der Kugel

G. Ringel · 1965

Earlier work this paper cites.

Crossing number is NP-complete

M. R. Garey and D. S. Johnson · 1983

Earlier work this paper cites.

The crossing number of a cubic plane polyhedral map plus an edge

A. Riskin · 1996

Earlier work this paper cites.

Computing crossing numbers in quadratic time

M. Grohe · 2004

Earlier work this paper cites.

Inserting an edge into a planar graph

C. Gutwenger, P. Mutzel, and R. Weiskircher · 2005

Earlier work this paper cites.

Planar crossing numbers of graphs embeddable in another surface

K. J. Börözky, J. Pach, and G. Tóth · 2006

Earlier work this paper cites.

Planar crossing numbers of genus g

H. Djidjev and I. Vrto · 2006

Earlier work this paper cites.

Crossing number is hard for cubic graphs

P. Hliněný · 2006

Cited alongside, same era.

On the crossing number of almost planar graphs

B. Mohar · 2006

Cited alongside, same era.

Approximating the crossing number of toroidal graphs

P. Hliněný and G. Salazar · 2007

Cited alongside, same era.

On the crossing number of almost planar graphs

P. Hliněný and G. Salazar · 2007

Cited alongside, same era.

Computing crossing number in linear time

K.-I. Kawarabayashi and B. Reed · 2007

Cited alongside, same era.

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

V. P. Korzhik and B. Mohar · 2008

Cited alongside, same era.

Adding one edge to planar graphs makes crossing number hard

S. Cabello and B. Mohar · 2010

Later among the works it cites.

Approximating the crossing number of graphs embeddable in any orientable surface

M. Chimani and P. Hliněný · 2010

Later among the works it cites.

Crossing and weighted crossing number of near-planar graphs

S. Cabello and B. Mohar · 2011

Later among the works it cites.

An algorithm for the graph crossing number problem

Original

J. Chuzhoy · 2011

Later among the works it cites.

Crossing numbers of graphs with rotation systems

M. J. Pelsmajer, M. Schaefer, and D. Štefankovic · 2011

Later among the works it cites.

Vertex insertion approximates the crossing number of apex graphs

M. Chimani, P. Hliněný, and P. Mutzel · 2012