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 ( n log n ) area using a sub-linear number of crossings per edge, and that for any given number ?>0 ? > 0 , every outerplanar graph admits an O(n1+?) O ( n 1 + ? ) area drawing with O(n1??) O ( n 1 ? ? ) crossing per edge. The drawing algorithms run in linear time and can be also generalized to another meaningful sub-family of seriesparallel graphs with bounded vertex-degree.
area requirement straight-line drawings outerplanar graphs seriesparallel graphs k-planar drawings