Logo der Fakultät Logo LG Theoretische Informatik
 

Veröffentlichung

Titel:

Drawing Trees and Triangulations with Few Geometric Primitives

AutorInnen: Gregor Hültenschmidt
Philipp Kindermann
Wouter Meulemans
André Schulz
Kategorie: Konferenzbandbeiträge
erschienen in: Proceedings of the 32nd European Workshop on Computational Geometry (EuroCG'16), pp. 55-58, Abstract
Abstract:

We define the visual complexity of a plane graph drawing to be the number of geometric objects needed to represent all its edges. In particular, one object may represent multiple edges (e.g. you need only one line segment to draw two collinear edges of the same vertex). 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. We also study the problem of drawing maximal triangulations with circular arcs and provide an algorithm to draw such graphs using only (5n - 11)/3 arcs. This provides a significant improvement over the lower bound of 2n for line segments for a nontrivial graph class.

Download: Extended Abstract
BibTeX-Eintrag: @InProceedings{hkms-dttfg-eurocg16, Title = {Drawing Trees and Triangulations with Few Geometric Primitives}, Author = {Gregor H{\"u}ltenschmidt and Philipp Kindermann and Wouter Meulemans and Andr{\'e} Schulz}, Booktitle = {Proceedings of the 32nd European Workshop on Computational Geometry (EuroCG'16)}, Year = {2016}, Editor = {Gill Barequet and Evanthia Papadopoulou}, Note = {Abstract}, Publisher = {Lugano}, Abstract = {We define the \emph{visual complexity} of a plane graph drawing to be the number of geometric objects needed to represent all its edges. In particular, one object may represent multiple edges (e.g. you need only one line segment to draw two collinear edges of the same vertex). 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. We also study the problem of drawing maximal triangulations with circular arcs and provide an algorithm to draw such graphs using only $(5n - 11)/3$ arcs. This provides a significant improvement over the lower bound of $2n$ for line segments for a nontrivial graph class.} }
Philipp Kindermann | 04.05.2017
FernUni-Logo FernUniversität in Hagen, LG Theoretische Informatik, 58084 Hagen