Drawing Planar Graphs with Few Geometric Primitives
Gregor Hültenschmidt, Philipp Kindermann, Wouter Meulemans, and André Schulz
Vol. 22, no. 2, pp. 357-387, 2018. Regular paper.
Abstract We define the 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.
Submitted: October 2017.
Reviewed: April 2018.
Revised: July 2018.
Accepted: July 2018.
Final: July 2018.
Published: August 2018.
Communicated by Antonios Symvonis
article (PDF)