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 ofG 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(n2logn) time in a real-RAM model and with at most n−k edges with at most 1+2left ceilingk/2right ceiling 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 k−3 bends on n−k edges.
Point-Set Embeddings of Trees with Given Partial Drawings
DI GIACOMO, Emilio;DIDIMO, WALTER;LIOTTA, Giuseppe;
2009
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 G′subset ofG 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(n2logn) time in a real-RAM model and with at most n−k edges with at most 1+2left ceilingk/2right ceiling 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 k−3 bends on n−k edges.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
