MIP-1207

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",
year=2012
number={MIP-1207}
}

Abstract

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

MIP-1207.pdf