Tradeoffs between Bends and Displacement in Anchored Graph Drawing.
Martin Fink, Subhash Suri · 2015
Many graph drawing applications entail geographical constraints on positions of vertices; these constraints can be at odds with aesthetic requirements such as the use of straight-line edges or the number of crossings. Without positional constraints on vertices, of course, every planar graph can be drawn crossing-free with straight-line edges. On the other hand, inflexible and precise specification of all vertex positions essentially leaves no room for presenting the graph in an aesthetically pleasing drawing. However, small deviations from precise vertex positions can often be tolerated, and so a natural middle ground is to impose soft positional constraints on vertices and then optimize for an appropriate aesthetic criterion. We explore one such trade-off: the amount of vertex position displacement vs. the number of bends in planar polyline drawings. In particular, let G = (V,E) be a planar graph, where each vertex v has a specified (target) position α(v). We wish to draw G so that no vertex is placed at distance more than δ from its target position and no edge has more than b bends. Given a bound on b, what is the smallest value of δ achievable for all n-vertex planar graphs? Our main result establishes that δ = Θ(n) is both necessary and sufficient if b is constant. We also derive trade-offs between δ and b. 1