We study the problem of computing leveled tree drawings, i.e., straight-line drawings of trees where the vertices have distinct preassigned y-coordinates. Our optimization goal is to maximize the crossing angle resolution (i.e., the minimum angle formed by any two crossing edges) and/or the vertex angle resolution (i.e., the minimum angle formed by two edges incident to the same vertex) of the drawing. We provide tight and almost tight worst case bounds for the crossing angle resolution and for the total angle resolution (i.e., the minimum of crossing and vertex angle resolution), respectively.

Vertex angle and crossing angle resolution of leveled tree drawings

DIDIMO, WALTER;LIOTTA, Giuseppe;
2012

Abstract

We study the problem of computing leveled tree drawings, i.e., straight-line drawings of trees where the vertices have distinct preassigned y-coordinates. Our optimization goal is to maximize the crossing angle resolution (i.e., the minimum angle formed by any two crossing edges) and/or the vertex angle resolution (i.e., the minimum angle formed by two edges incident to the same vertex) of the drawing. We provide tight and almost tight worst case bounds for the crossing angle resolution and for the total angle resolution (i.e., the minimum of crossing and vertex angle resolution), respectively.
2012
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11391/909617
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 5
social impact