Title: Drawing Planar Graphs with Few Geometric Primitives,
Abstract: We define the \emph{visual complexity} of a plane graph drawing to be the
number of basic geometric objects needed to represent all its edges. In
particular, one object may represent multiple edges (e.g., one needs only one
line segment to draw a path with an arbitrary number of edges). Let $n$ denote
the number of vertices of a graph. We show that trees can be drawn with $3n/4$
straight-line segments on a polynomial grid, and with $n/2$ straight-line
segments on a quasi-polynomial grid. Further, we present an algorithm for
drawing planar 3-trees with $(8n-17)/3$ segments on an $O(n)\times O(n^2)$
grid. This algorithm can also be used with a small modification to draw maximal
outerplanar graphs with $3n/2$ edges on an $O(n)\times O(n^2)$ grid. We also
study the problem of drawing maximal planar graphs with circular arcs and
provide an algorithm to draw such graphs using only $(5n - 11)/3$ arcs. This is
significantly smaller than the lower bound of $2n$ for line segments for a
nontrivial graph class.