A mixed graph has both directed and undirected edges. We study how to compute a crossing-free drawing of a planar embedded mixed graph, such that it is upward “as much as possible”. Roughly speaking, in an upward drawing of a mixed graph all edges are monotone in the vertical direction and directed edges flow monotonically from bottom to top according to their orientation. We study quasi-upward drawings of mixed graphs, that is, upward drawings where edges can break the vertical monotonicity in a finite number of edge points, called bends. We describe both efficient heuristics and exact methods for computing quasi-upward planar drawings of planar embedded mixed graphs with few bends, and we extensively compare them experimentally: the results show the effectiveness of our algorithms in many cases.
Quasi-Upward Planar Drawings of Mixed Graphs with Few Bends: Heuristics and Exact Methods.
BINUCCI, Carla;DIDIMO, WALTER
2014
Abstract
A mixed graph has both directed and undirected edges. We study how to compute a crossing-free drawing of a planar embedded mixed graph, such that it is upward “as much as possible”. Roughly speaking, in an upward drawing of a mixed graph all edges are monotone in the vertical direction and directed edges flow monotonically from bottom to top according to their orientation. We study quasi-upward drawings of mixed graphs, that is, upward drawings where edges can break the vertical monotonicity in a finite number of edge points, called bends. We describe both efficient heuristics and exact methods for computing quasi-upward planar drawings of planar embedded mixed graphs with few bends, and we extensively compare them experimentally: the results show the effectiveness of our algorithms in many cases.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
