Anchored Drawings of Planar Graphs - Graph Drawing - page 403

Anchored Drawings of Planar Graphs

Patrizio Angelini 1 , Giordano Da Lozzo 1 , Marco Di Bartolomeo 1 ,
Giuseppe Di Battista 1 , Seok-Hee Hong 2 ,Maurizio Patrignani 1 , and Vincenzo Roselli 1

1

Department of Engineering, Roma Tre University, Italy
{ angelini,dalozzo,dibartolomeo,gdb,
patrigna,roselli } @dia.uniroma3.it

2

School of Information Technologies, The University of Sydney, Australia
[e-mail]

Abstract. In this paper we study the A NCHORED G RAPH D RAWING (AGD)
problem: Given a planar graph G , an initial placement for its vertices, and a dis-
tance 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 NP-hard in several settings and provide
a polynomial-time algorithm when d is the uniform distance L ∞ and edges are
required to be drawn as horizontal or vertical segments.

1 Introduction

Several applications require to draw graphs whose vertices are constrained to be not
too much distant from specific points [1,9]. As an example, consider a graph whose
vertices are cities and whose edges are relationships between cities. It is conceivable
that the user wants to draw the graph on a geographic map where vertices have the
coordinates of the corresponding cities. Unfortunately, depending on the local density
of the cities, the drawing may be cluttered or may contain crossings between edges that
might disappear if the vertices could move from their locations. Hence, the user may be
interested to trade precision for quality of the drawing, accepting that the vertices move
of a certain distance from the location of the cities, provided that the readability of the
drawing increases. Problems in which the input consists of a set of imprecise points
have also been studied in Computational Geometry [4,7].
In this paper we consider the following problem, that we call A NCHORED G RAPH
D RAWING (AGD ) 1 .Givenagraph G =( V,E ), an initial placement for its vertices,
and a distance ʴ , we ask whether there exists a planar drawing of G , according to a
certain drawing convention, such that each vertex v V can move at distance at most

ʴ from its initial placement. Note that the problem can have different formulations de-
pending on how the concepts of “readability” and “distance” are defined.
We consider both straight-line planar drawings and rectilinear planar drawings. Fur-
ther, in addition to the traditional L 2 Euclidean distance, we consider the L 1 Manhattan
Work partially supported by ESF EuroGIGA GraDR, by the MIUR project AMANDA “Al-
gorithmics for MAssive and Networked DAta”, prot. 2012C4E3KT 001, and by the EU FP7
STREPProject ”Leone: From Global Measurements to Local Management”, no. 317647.

∈

1

We remark that the term 'anchored graph' was used within a different setting in [3].