Drawing trees and triangulations with few geometric primitives

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

Drawing trees and triangulations with few geometric primitives

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

Research output: Contribution to conference › Paper › Academic

207 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 language	English
Pages	31-34
Number of pages	4
Publication status	Published - 2016
Externally published	Yes
Event	32nd European Workshop on Computational Geometry (EuroCG 2016) - Lugano, Switzerland Duration: 30 Mar 2016 → 1 Apr 2016 Conference number: 32 http://www.eurocg2016.usi.ch/

Workshop

Workshop	32nd European Workshop on Computational Geometry (EuroCG 2016)
Abbreviated title	EuroCG 2016
Country/Territory	Switzerland
City	Lugano
Period	30/03/16 → 1/04/16
Internet address	http://www.eurocg2016.usi.ch/

Access to Document

Author final versionFinal author version , 341 KB

Cite this

@conference{ca58eba1e84a4906b77cd6fb2e39f2c1,

title = "Drawing trees and triangulations with few geometric primitives",

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",

author = "G. H{\"u}ltenschmidt and P. Kindermann and W. Meulemans and A. Schulz",

year = "2016",

language = "English",

pages = "31--34",

note = "32nd European Workshop on Computational Geometry (EuroCG 2016), EuroCG 2016 ; Conference date: 30-03-2016 Through 01-04-2016",

url = "http://www.eurocg2016.usi.ch/",

}

TY - CONF

T1 - Drawing trees and triangulations with few geometric primitives

AU - Hültenschmidt, G.

AU - Kindermann, P.

AU - Meulemans, W.

AU - Schulz, A.

N1 - Conference code: 32

PY - 2016

Y1 - 2016

N2 - 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

AB - 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

M3 - Paper

SP - 31

EP - 34

T2 - 32nd European Workshop on Computational Geometry (EuroCG 2016)

Y2 - 30 March 2016 through 1 April 2016

ER -

Drawing trees and triangulations with few geometric primitives

Abstract

Workshop

Access to Document

Fingerprint

Cite this