Anchored Drawings of Planar Graphs - Graph Drawing - page 404

Ta b l e 1 . The complexity of the A NCHORED G RAPH D RAWING problem depending on the metric
and drawing style adopted when the areas of the vertices do not overlap

Metric Distance Region Shape Straight-line Rectilinear

L 1 Manhattan NP-hard NP-hard

L 2 Euclidean NP-hard NP-hard

L ∞ Uniform NP-hard Polynomial

distance and the L ∞ 'uniform' distance. Note that, adopting L 2 distance is equivalent to
allowing vertices to be placed into circular regions centered at their original positions,
and adopting L 1 or L ∞ distances is equivalent to allowing vertices to be placed into
diamond-shaped or square-shaped areas, respectively.
Observe that, if the regions of two vertices overlap, the positions of the two vertices
can be swapped with respect to their initial placement, which may be confusing to a user
of the drawing. Moreover, overlapping between vertex regions would make problem
AGD as difficult as known Clustered Planarity variants, such as the Strip Planarity
problem [2] in the straight-line setting, whose complexity is a non-trivial open problem.
Hence, we restrict to instances such that the regions of the vertices do not overlap.
We remark that the version of the problem where each circle may have a different size
was shown to be NP-hard in [6] by reducingPlanar-(3 , 4)-SAT with variable repetitions
(where repeated occurrences of one variable in one clause are counted repeatedly). The
proof in [6] uses disks with radius zero and disks with large radii. Also, the reduction
relies on overlapping disks.
Furthermore, we observe that the NP-hardness of the problem with different dis-
tances and overlapping areas trivially follows from the NP-hardness of extending apla-
nar straight-line drawing [10] by setting ʴ ( v )=0for each fixed vertex v and allowing
suitably large distances for vertices that have to be planarly added to the drawing.
In this paper we show that the A NCHORED G RAPH D RAWING problem is NP-hard
for any combination of metrics and drawing standards that we considered, with the ex-
ception of rectilinear drawingsanduniform distance metric (square-shaped regions).
These results, summarized in Table 1, were somehow unexpected, as computing apla-
nar rectilinear drawing of a graph, withoutanyfurther constraint, is NP-hard [5].
The paper is organized as follows. Section 2 contains basic definitions and termi-
nology. Section 3 describes a polynomial-time algorithm when the considered distance
is the uniform distance L ∞ and edges are required to be drawn as either horizontal
or vertical segments. Section 4 is devoted to the NP-hardness proofs of all the other
considered settings of the problems. Finally, Section 5 discusses some open problems.

2 Problem Definition and Instances Classification

A straight-lineplanardrawing of a graph G is a drawing of G where edges are straight-
line segments that do not intersect except at common end-points. A rectilinearplanar
drawing is a straight-line planar drawing where edges are parallel to the axes.
Given two points p and q in the plane, denote by dx ( p,q ) and dy ( p,q ) the differences
of their coordinates, i.e., dx ( p,q )= | x ( p ) − x ( q ) | and dy ( p,q )= | y ( p ) − y ( q ) | ,where