Embedding Plane 3Trees in ℝ2 and ℝ3Durocher, Stephane and Mondal, Debajyoti and Nishat, Rahnuma Islam and Rahman, Md. Saidur and Whitesides, Sue (2012) Embedding Plane 3Trees in ℝ2 and ℝ3. In: Graph Drawing 19th International Symposium, GD 2011, September 2123, 2011 , pp. 3951(Official URL: http://dx.doi.org/ 10.1007/9783642258787_5). Full text not available from this repository.
Official URL: http://dx.doi.org/ 10.1007/9783642258787_5
AbstractA pointset embedding of a planar graph G with n vertices on a set P of n points in Rd , d ≥ 1, is a straightline drawing of G, where the vertices of G are mapped to distinct points of P . The problem of computing a pointset embedding of G on P is NPcomplete in R2 , even when G is 2outerplanar and the points are in general position. On the other hand, if the points of P are in general position in R3 , then any bijective mapping of the vertices of G to the points of P determines a pointset embedding of G on P . In this paper, we give an O(n4/3+ )expected time algorithm to decide whether a plane 3tree with n vertices admits a pointset embedding on a given set of n points in general position in R2 and compute such an embedding if it exists, for any fixed >0. We extend our algorithm to embed a subclass of 4trees on a point set in R3 in the form of nested tetrahedra. We also prove that given a plane 3tree G with n vertices, a set P of n points in R3 that are not necessarily in general position and a mapping of the three outer vertices of G to three different points of P , it is NPcomplete to decide if G admits a pointset embedding on P respecting the given mapping.
Actions (login required)
