Drawing planar graphs with few geometric primitives

Gregor Hültenschmidt, Philipp Kindermann, Wouter Meulemans, André Schulz

Research output: Contribution to journalArticleAcademicpeer-review

4 Citations (Scopus)
79 Downloads (Pure)

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)×O(n2) grid. This algorithm can also be used with a small modification to draw maximal outerplanar graphs with 3n/2 edges on an O(n)×O(n2) 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.
Original languageEnglish
Pages (from-to)357-387
Number of pages31
JournalJournal of Graph Algorithms and Applications
Volume22
Issue number2
DOIs
Publication statusPublished - 2018

Fingerprint

Dive into the research topics of 'Drawing planar graphs with few geometric primitives'. Together they form a unique fingerprint.

Cite this