PointSet Embeddability of 2Colored TreesFrati, Fabrizio and Glisse, Marc and Lenhart, William J. and Liotta, Giuseppe and Mchedlidze, Tamara and Nishat, Rahnuma Islam (2013) PointSet Embeddability of 2Colored Trees. In: 20th International Symposium, GD 2012, September 1921, 2012 , pp. 291302(Official URL: http://link.springer.com/chapter/10.1007/9783642...). Full text not available from this repository.
Official URL: http://link.springer.com/chapter/10.1007/9783642...
AbstractIn this paper we study bichromatic pointset embeddings of 2colored trees on 2colored point sets, i.e., pointset embeddings of trees (whose vertices are colored red and blue) on point sets (whose points are colored red and blue) such that each red (blue) vertex is mapped to a red (resp. blue) point. We prove that deciding whether a given 2colored tree admits a bichromatic pointset embedding on a given convex point set is an complete problem; we also show that the same problem is lineartime solvable if the convex point set does not contain two consecutive points with the same color. Furthermore, we prove a 3n/2 − O(1) lower bound and a 2n upper bound (a 7n/6 − O(logn) lower bound and a 4n/3 upper bound) on the minimum size of a universal point set for straightline bichromatic embeddings of 2colored trees (resp. 2colored binary trees). Finally, we show that universal convex point sets with n points exist for 1bend bichromatic pointset embeddings of 2colored trees.
Actions (login required)
