Anchored Drawings of Planar Graphs

Angelini, Patrizio and Da Lozzo, Giordano and Di Bartolomeo, Marco and Di Battista, Giuseppe and Hong, Seok-Hee and Patrignani, Maurizio and Roselli, Vincenzo (2014) Anchored Drawings of Planar Graphs. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014, Würzburg, Germany , pp. 404-415 (Official URL: http://dx.doi.org/10.1007/978-3-662-45803-7_34).

Full text not available from this repository.

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 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.

Item Type:Conference Paper
Additional Information:10.1007/978-3-662-45803-7_34
Classifications:G Algorithms and Complexity > G.560 Geometry
P Styles > P.540 Planar
P Styles > P.600 Poly-line > P.600.700 Orthogonal
P Styles > P.720 Straight-line
Z Theory > Z.250 Geometry
Z Theory > Z.750 Topology
ID Code:1450

Repository Staff Only: item control page

References

Abellanas, M., Aiello, A., Hernández, G., Silveira, R.I.: Network drawing with geographical constraints on vertices. In: Actas XI Encuentros de Geom. Comput., pp. 111–118 (2005)

Angelini, P., Da Lozzo, G., Di Battista, G., Frati, F. Strip planarity testing. In: Wismath, S., Wolff, A. eds. (2013) Graph Drawing. Springer, Heidelberg, pp. 37-48

Cabello, S., Mohar, B. (2013) Adding one edge to planar graphs makes crossing number and 1-planarity hard. SIAM J. Comput. 42: pp. 1803-1829

Dumitrescu, A., Mitchell, J.S.B. (2003) Approximation algorithms for TSP with neighborhoods in the plane. J. Algorithms 48: pp. 135-159

Garg, A., Tamassia, R. (2001) On the computational complexity of upward and rectilinear planarity testing. SIAM J. Comput. 31: pp. 601-625

Godau, M. On the difficulty of embedding planar graphs with inaccuracies. In: Tamassia, R., Tollis, I.G. eds. (1995) Graph Drawing. Springer, Heidelberg, pp. 254-261

Löffler, M., Kreveld, M.J. (2010) Largest and smallest convex hulls for imprecise points. Algorithmica 56: pp. 235-269

Lichtenstein, D. (1982) Planar formulae and their uses. SIAM J. Comput. 11: pp. 185-225

Lyons, K.A., Meijer, H., Rappaport, D.: Algorithms for cluster busting in anchored graph drawing. J. Graph Algorithms Appl. 2(1) (1998)

Patrignani, M. (2006) On extending a partial straight-line drawing. International Journal of Foundations of Computer Science (IJFCS) 17: pp. 1061-1069