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 , 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
Divisions: UNSPECIFIED
Depositing User: Administration GDEA
Date Deposited: 22 May 2015 12:47
Last Modified: 22 May 2015 12:47
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1450

Actions (login required)

View Item View Item