1. Point-set embeddings of trees with given partial drawings
- Author
-
Di Giacomo, Emilio, Didimo, Walter, Liotta, Giuseppe, Meijer, Henk, and Wismath, Stephen K.
- Subjects
- *
EMBEDDINGS (Mathematics) , *TREE graphs , *GRAPH theory , *SET theory , *PLANE geometry , *MATHEMATICAL mappings , *LINE geometry - Abstract
Abstract: 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 on a subset of S. The desired output is a point-set embedding of G on S that includes the given partial drawing of . We concentrate on trees and show how to compute the output in time in a real-RAM model and with at most edges with at most bends, 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 bends on edges. [Copyright &y& Elsevier]
- Published
- 2009
- Full Text
- View/download PDF