Home Issues About JGAA Instructions for Authors
 
DOI: 10.7155/jgaa.00347
1-Planarity of Graphs with a Rotation System
Christopher Auer, Franz J. Brandenburg, Andreas Gleißner, and Josef Reislhuber
Vol. 19, no. 1, pp. 67-86, 2015. Regular paper.
Abstract A graph is 1-planar if it can be drawn in the plane such that each edge is crossed at most once. 1-planarity is known NP-hard, even for graphs of bounded bandwidth, pathwidth, or treewidth, and for near-planar graphs in which an edge is added to a planar graph. On the other hand, there is a linear time 1-planarity testing algorithm for maximal 1-planar graphs with a given rotation system. In this work, we show that 1-planarity remains NP-hard even for 3-connected graphs with (or without) a rotation system. Moreover, the crossing number problem remains NP-hard for 3-connected 1-planar graphs with (or without) a rotation system.
Submitted: August 2014.
Reviewed: January 2015.
Revised: January 2015.
Accepted: January 2015.
Final: January 2015.
Published: January 2015.
Communicated by Giuseppe Liotta
article (PDF)
BibTeX