1-Planarity of Graphs with a Rotation System

Authors

  • Christopher Auer
  • Franz Brandenburg
  • Andreas Gleißner
  • Josef Reislhuber

DOI:

https://doi.org/10.7155/jgaa.00347

Keywords:

graph drawing , 1-planarity , rotation system , NP-hardness

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.

Downloads

Download data is not yet available.

Downloads

Published

2015-01-01

How to Cite

Auer, C., Brandenburg, F., Gleißner, A., & Reislhuber, J. (2015). 1-Planarity of Graphs with a Rotation System. Journal of Graph Algorithms and Applications, 19(1), 67–86. https://doi.org/10.7155/jgaa.00347

Issue

Section

Articles

Categories