Di Giacomo, Emilio and Didimo, Walter and Liotta, Giuseppe and Meijer, Henk and Wismath, Stephen (2008) Point-Set Embedding of Trees with Edge Constraints. [Conference Paper]
Full text not available from this repository.
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 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 |
|---|---|
| Classifications: | M Methods > M.900 Tree G Algorithms and Complexity > G.490 Embeddings |
| ID Code: | 833 |
| Deposited By: | GDEA, Administration |
| Deposited On: | 24 Jun 2008 |
| Last Modified: | 18 Sep 2008 13:09 |
| Alternative Locations: | http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=4875&spage=113 |
Repository Staff Only: item control page
