Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10327389 | Computational Geometry | 2013 | 8 Pages |
Abstract
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(n1+ε) area drawing with O(n1âε) 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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta, Fabrizio Montecchiani,