Embedding Plane 3-Trees in ℝ2 and ℝ3

Durocher, Stephane and Mondal, Debajyoti and Nishat, Rahnuma Islam and Rahman, Md. Saidur and Whitesides, Sue (2012) Embedding Plane 3-Trees in ℝ2 and ℝ3. In: Graph Drawing 19th International Symposium, GD 2011, September 21-23, 2011, Eindhoven, The Netherlands , pp. 39-51 (Official URL: http://dx.doi.org/ 10.1007/978-3-642-25878-7_5).

Full text not available from this repository.


A point-set embedding of a planar graph G with n vertices on a set P of n points in Rd , d ≥ 1, is a straight-line drawing of G, where the vertices of G are mapped to distinct points of P . The problem of computing a point-set embedding of G on P is NP-complete in R2 , even when G is 2-outerplanar 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 point-set embedding of G on P . In this paper, we give an O(n4/3+ )-expected time algorithm to decide whether a plane 3-tree with n vertices admits a point-set 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 4-trees on a point set in R3 in the form of nested tetrahedra. We also prove that given a plane 3-tree 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 NP-complete to decide if G admits a point-set embedding on P respecting the given mapping.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-25878-7_5
Classifications:G Algorithms and Complexity > G.490 Embeddings
M Methods > M.900 Tree
ID Code:1239

Repository Staff Only: item control page


Bose, P.: On embedding an outer-planar graph in a point set. Computational Geometry: Theory and Applications 23(3), 303–312 (2002)

Bose, P., McAllister, M., Snoeyink, J.: Optimal algorithms to embed trees in a point set. Journal of Graph Algorithms and Applications 1(2), 1–15 (1997)

Cabello, S.: Planar embeddability of the vertices of a graph using a fixed point set is NP-hard. Journal of Graph Algorithms and Applications 10(2), 353–363 (2006)

Castañeda, N., Urrutia, J.: Straight line embeddings of planar graphs on point sets. In: Proc. of CCCG, pp. 312–318 (1996)

Chazelle, B., Sharir, M., Welzl, E.: Quasi-optimal upper bounds for simplex range searching and new zone theorems. Algorithmica 8(5&6), 407–429 (1992)

Demaine, E.D., Schulz, A.: Embedding stacked polytopes on a polynomial-size grid. In: Proc. of ACM-SIAM SODA, pp. 77–80 (2011)

Garey, M.R., Johnson, D.S.: Computers and intractability. Freeman, San Francisco (1979)

Giacomo, E.D., Didimo, W., Liotta, G., Meijer, H., Wismath, S.K.: Constrained point-set embeddability of planar graphs. International Journal of Computational Geometry and Applications 20(5), 577–600 (2010)

Kaufmann, M., Wiese, R.: Embedding vertices at points: Few bends suffice for planar graphs. Journal of Graph Algorithms and Applications 6(1), 115–129 (2002)

Moosa, T.M., Rahman, M.S.: Improved algorithms for the point-set embeddability problem for plane 3-trees. CoRR abs/1012.0230 (2010), http://arxiv.org/abs/1012.0230

Nishat, R.I., Mondal, D., Rahman, M. S.: Point-set embeddings of plane 3-trees. In: Brandes, U., Cornelsen, S. (eds.) GD 2010. LNCS, vol. 6502, pp. 317–328. Springer, Heidelberg (2011)

Pach, J., Wenger, R.: Embedding planar graphs at fixed vertex locations. Graphs and Combinatorics 17(4), 717–728 (2001)