Computing quasi-upward planar drawings of mixed graphs

C Binucci, W Didimo - The Computer Journal, 2016 - academic.oup.com
The Computer Journal, 2016academic.oup.com
A mixed graph has both directed and undirected edges. We study how to compute a
crossing-free drawing of an embedded planar mixed graph, such that it is upward 'as much
as possible'. Roughly speaking, in an upward drawing of a mixed graph all (undirected)
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 …
Abstract
A mixed graph has both directed and undirected edges. We study how to compute a crossing-free drawing of an embedded planar mixed graph, such that it is upward ‘as much as possible’. Roughly speaking, in an upward drawing of a mixed graph all (undirected) 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 heuristic techniques and exact approaches for computing quasi-upward planar drawings of embedded mixed graphs with few bends, and we extensively compare them experimentally: the results suggest that our algorithms are effective in many cases.
Oxford University Press
以上显示的是最相近的搜索结果。 查看全部搜索结果