Minimum Length Embedding of Planar Graphs at Fixed Vertex Locations

Chan, Timothy M. and Hoffmann, Hella-Franziska and Kiazyk, Stephen and Lubiw, Anna (2013) Minimum Length Embedding of Planar Graphs at Fixed Vertex Locations. In: 21st International Symposium, GD 2013, September 23-25, 2013 , pp. 376-387(Official URL: http://dx.doi.org/10.1007/978-3-319-03841-4_33).

Full text not available from this repository.

Abstract

We consider the problem of finding a planar embedding of a graph at fixed vertex locations that minimizes the total edge length. The problem is known to be NP-hard. We give polynomial time algorithms achieving an O(n√logn) approximation for paths and matchings, and an O(n) approximation for general graphs.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.560 Geometry
G Algorithms and Complexity > G.070 Area / Edge Length
Divisions: UNSPECIFIED
Depositing User: Administration GDEA
Date Deposited: 13 Aug 2014 15:45
Last Modified: 13 Aug 2014 15:45
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1390

Actions (login required)

View Item View Item