Upward drawing is a widely studied drawing convention for the visual representation of directed graphs. In an upward drawing vertices are mapped to distinct points of the plane, and edges are curves monotonically increasing in the vertical direction, according to their orientation. In particular, not all planar digraphs admit an upward planar drawing (i.e., an upward drawing with no edge crossing), and testing whether a planar digraph is upward planar drawable is NP-hard. Furthermore, straight-line upward planar drawings may require exponential area. In this paper we study a relaxation of upward drawings, called upward-rightward drawings; in such a drawing for any directed path from a vertex u to a vertex v it must be that either v is above u or v is to the right of u. In contrast with upward planarity, we prove that every planar digraph admits an upward-rightward planar drawing with straight-line edges and that this drawing can be computed in linear time and polynomial area.

Upward-rightward planar drawings

DI GIACOMO, Emilio;DIDIMO, WALTER;LIOTTA, Giuseppe;MONTECCHIANI, FABRIZIO
2014

Abstract

Upward drawing is a widely studied drawing convention for the visual representation of directed graphs. In an upward drawing vertices are mapped to distinct points of the plane, and edges are curves monotonically increasing in the vertical direction, according to their orientation. In particular, not all planar digraphs admit an upward planar drawing (i.e., an upward drawing with no edge crossing), and testing whether a planar digraph is upward planar drawable is NP-hard. Furthermore, straight-line upward planar drawings may require exponential area. In this paper we study a relaxation of upward drawings, called upward-rightward drawings; in such a drawing for any directed path from a vertex u to a vertex v it must be that either v is above u or v is to the right of u. In contrast with upward planarity, we prove that every planar digraph admits an upward-rightward planar drawing with straight-line edges and that this drawing can be computed in linear time and polynomial area.
2014
9781479961702
9781479961719
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/1293898
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 4
social impact