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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

135 Downloads (Pure)

Samenvatting

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

Originele taal-2	Engels
Titel	Abstracts of the 32nd European Workshop on Computational Geometry (EuroCG)
Aantal pagina's	4
Status	Gepubliceerd - 2016
Extern gepubliceerd	Ja
Evenement	32nd European Workshop on Computational Geometry (EuroCG 2016) - Lugano, Zwitserland Duur: 30 mrt. 2016 → 1 apr. 2016 Congresnummer: 32 http://www.eurocg2016.usi.ch/

Workshop

Workshop	32nd European Workshop on Computational Geometry (EuroCG 2016)
Verkorte titel	EuroCG 2016
Land/Regio	Zwitserland
Stad	Lugano
Periode	30/03/16 → 1/04/16
Internet adres	http://www.eurocg2016.usi.ch/

Toegang tot document

Author final versionFinale auteursversie , 341 KB

Citeer dit

@inproceedings{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",

booktitle = "Abstracts of the 32nd European Workshop on Computational Geometry (EuroCG)",

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

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 - Conference contribution

BT - Abstracts of the 32nd European Workshop on Computational Geometry (EuroCG)

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

Samenvatting

Workshop

Toegang tot document

Vingerafdruk

Citeer dit