Point-Set Embedding of Trees with Edge Constraints

Di Giacomo, Emilio and Didimo, Walter and Liotta, Giuseppe and Meijer, Henk and Wismath, Stephen (2008) Point-Set Embedding of Trees with Edge Constraints. In: Graph Drawing 15th International Symposium, GD 2007, September 24-26, 2007 , pp. 113-124(Official URL: http://dx.doi.org/10.1007/978-3-540-77537-9_14).

Full text not available from this repository.


Given a graph G with n vertices and a set S of n points in the plane, a point-set embedding$ of G on S is a planar drawing such that each vertex of G is mapped to a distinct point of S. A geometric point-set embedding is a point-set embedding with no edge bends. This paper studies the following problem: The input is a set S of n points, a planar graph G with n vertices, and a geometric point-set embedding of a subgraph G' subset G on a subset of S. The desired output is a point-set embedding of G on S that includes the given partial drawing of G'. We concentrate on trees and show how to compute the output in O(n^2 log n) time and with at most 1 + 2 lceil k/2 rceil bends per edge, where k is the number of vertices of the given subdrawing. We also prove that there are instances of the problem which require at least k-3 bends for some of the edges.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-77537-9_14
Classifications: M Methods > M.900 Tree
G Algorithms and Complexity > G.490 Embeddings
URI: http://gdea.informatik.uni-koeln.de/id/eprint/833

Actions (login required)

View Item View Item