PointSet Embedding of Trees with Edge ConstraintsDi Giacomo, Emilio and Didimo, Walter and Liotta, Giuseppe and Meijer, Henk and Wismath, Stephen (2008) PointSet Embedding of Trees with Edge Constraints. In: Graph Drawing 15th International Symposium, GD 2007, September 2426, 2007 , pp. 113124(Official URL: http://dx.doi.org/10.1007/9783540775379_14). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783540775379_14
AbstractGiven a graph G with n vertices and a set S of n points in the plane, a pointset 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 pointset embedding is a pointset 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 pointset embedding of a subgraph G' subset G on a subset of S. The desired output is a pointset 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 k3 bends for some of the edges.
Actions (login required)
