Fakultät für Informatik und Mathematik


Paper Description

BibTeX entry

@ incollection{MIP-1207,
author="C. Auer, F. J. Brandenburg, A. Gleissner, J. Reislhuber"
title="On 1-Planar Graphs with Rotation Systems"
institution="Fakult{\"a}t f{\"u}r Informatik und Mathematik, Universit{\"a}t Passau",


A graph is 1-planar if it can be drawn in the plane such that each edge is crossed at most once. This causes essential distinctions to planar graphs: planarity can be tested in linear time whereas 1-planarity is NP-hard. We improve this result and show the NP-hardness for 1-planar graphs with a given rotation system. In addition, the crossing number problem remains NP-hard for 1-planar graphs even with a rotation system. However, there are tractable cases: 1-planarity can be tested efficiently for embedded graphs and for maximal graphs with a given rotation system.

Paper itself