Information Technology Reference
In-Depth Information
Otherwise, if at least one of the literals is set to
true
, then an anchored drawing of
Ęł
can be realized (see Fig. 7(c) for an example).
Theorem 3.
AGD
-
L
2
-
is NP-hard.
Proof sketch:
To prove hardness we reduce problem P3SAT to AGD-
L
2
-
R
, un-
der the hypothesis that Property A is satisfied (no overlap among vertex regions). The
adopted gadgets are similar to those used in the proof of Theorem 2 with the exception
of the clause gadget. That gadget is based on creating three horizontal strips that are the
only possible containers of a specific edge. If all the literals are
false
,thensuitable
edges obstruct such strips and make it not possible to construct an anchored drawing.
R
5
Conclusions and Open Problems
We considered the A
NCHORED
G
RAPH
D
RAWING
problem in several settings, show-
ing that, provided that the input instance do not have overlaps between vertex regions
(Property A), the problem of producing planar drawingsisNP-hard in most of the set-
tings. The only exception is for the case with rectilinear drawingsanduniform dis-
tances (square-shaped regions), for which a polynomial-time algorithm is provided in
Section 3.
We leave open the following questions: (
i
) Does problem AGD belong to class NP?
(
ii
) The instances in ourNP-hardness proofs can be augmented to equivalent instances
whose graphs are biconnected (we omit details for space reasons). In these instances,
different truth values correspond to different embeddings. What is the complexity of
AGD when the input graph is triconnected or has at least a fixed embedding? (
iii
) What
if we allow the vertex regions to (at least partially) overlap?
References
1. Abellanas, M., Aiello, A., Hernandez, G., Silveira, R.I.: Network drawing with geographical
constraints on vertices. In: Actas XI Encuentros de Geom. Comput., pp. 111-118 (2005)
2. Angelini, P., Da Lozzo, G., Di Battista, G., Frati, F.: Strip planarity testing. In: Wismath, S.,
Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 37-48. Springer, Heidelberg (2013)
3. Cabello, S., Mohar, B.: Adding one edgetoplanargraphs makes crossing number and 1-
planarity hard. SIAM J. Comput. 42(5), 1803-1829 (2013)
4. Dumitrescu, A., Mitchell, J.S.B.: Approximation algorithms for TSP with neighborhoods in
the plane. J. Algorithms 48(1), 135-159 (2003)
5. Garg, A., Tamassia, R.: On the computational complexity of upward and rectilinear planarity
testing.SIAMJ.Comput. 31(2), 601-625 (2001)
6. Godau, M.: On the difficulty of embedding planar graphs with inaccuracies. In: Tamassia,
R., Tollis, I.G. (eds.) GD 1994. LNCS, vol. 894, pp. 254-261. Springer, Heidelberg (1995)
7. L offler, M., van Kreveld, M.J.: Largest and smallest convex hulls for imprecise points. Algo-
rithmica 56(2), 235-269 (2010)
8. Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11, 185-225 (1982)
9. Lyons, K.A., Meijer, H., Rappaport, D.: Algorithms for cluster busting in anchored graph
drawing.J.GraphAlgorithms Appl. 2(1) (1998)
10. Patrignani, M.: On extending a partial straight-line drawing. International Journal of Foun-
dations of Computer Science (IJFCS) 17(5), 1061-1069 (2006)
