Anchored Drawings of Planar Graphs

Abstract

In this paper we study the ANCHORED GRAPH DRAWING (AGD) problem$:$ Given a planar graph $G$, an initial placement for its vertices, and a distance $d$, produce a planar straight-line drawing of $G$ such that each vertex is at distance at most $d$ from its original position. We show that the AGD problem is $\mathcal{NP}$-hard in several settings and provide a polynomial-time algorithm when $d$ is the uniform distance $L_\infty$ and edges are required to be drawn as horizontal or vertical segments.