Drawing trees and triangulations with few geometric primitives

G. Hültenschmidt, P. Kindermann, W. Meulemans, A. Schulz

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

19 Downloads (Pure)

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 planar graphs 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
Original languageEnglish
Title of host publicationAbstracts of the 32nd European Workshop on Computational Geometry (EuroCG)
Number of pages4
Publication statusPublished - 2016
Externally publishedYes
Event32nd European Workshop on Computational Geometry (EuroCG 2016) - Lugano, Switzerland
Duration: 30 Mar 20161 Apr 2016
Conference number: 32
http://www.eurocg2016.usi.ch/

Workshop

Workshop32nd European Workshop on Computational Geometry (EuroCG 2016)
Abbreviated titleEuroCG 2016
CountrySwitzerland
CityLugano
Period30/03/161/04/16
Internet address

Fingerprint Dive into the research topics of 'Drawing trees and triangulations with few geometric primitives'. Together they form a unique fingerprint.

Cite this