Area requirement of graph drawings with few crossings per edge

摘要

In this paper we study how to compute compact straight-line drawings of planar graphs with a limited number of crossings per edge. We prove that every outerplanar graph can be drawn in O(nlogn) area using a sub-linear number of crossings per edge, and that for any given number ε>0, every outerplanar graph admits an O(n~(1+ε)) area drawing with O(n~(1 -ε)) crossing per edge. The drawing algorithms run in linear time and can be also generalized to another meaningful sub-family of series-parallel graphs with bounded vertex-degree.