Edge offset in drawings of layered graphs with evenly-spaced nodes on each layer
Matthias F. M. Stallmann · NCSU Libraries Repository (North Carolina State University Libraries) · 2016
Minimizing edge lengths is an important esthetic criterion in graph drawings.In a layered graph drawing method the total length of edges can be minimized at any of several points in the drawing process.Here we focus on edge offset, a measure closely related to edge length -we call it stretch.And we consider minimizing stretch when the permutation of nodes on each layer is determined, usually the point at which edge crossings are minimized.If we fix x-coordinates so as to distribute nodes evenly on each layer we can then permute nodes and use the permutations to assign nodes to these fixed x-coordinates with the objective of minimizing total stretch.We show that (a) the problem of minimizing stretch in this setting is NP-hard; (b) there exists a straightforward mixed integer program for stretch minimization; and (c) any heuristic or algorithm that minimizes or attempts to minimize crossings has asymptotic approximation ratio at least 2 when it comes to stretch.