Point-Set Embeddability of 2-Colored Trees

Frati, Fabrizio and Glisse, Marc and Lenhart, William J. and Liotta, Giuseppe and Mchedlidze, Tamara and Nishat, Rahnuma Islam (2013) Point-Set Embeddability of 2-Colored Trees. In: 20th International Symposium, GD 2012, September 19-21, 2012 , pp. 291-302(Official URL: http://link.springer.com/chapter/10.1007/978-3-642...).

Full text not available from this repository.


In this paper we study bichromatic point-set embeddings of 2-colored trees on 2-colored point sets, i.e., point-set 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 2-colored tree admits a bichromatic point-set embedding on a given convex point set is an  -complete problem; we also show that the same problem is linear-time 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 straight-line bichromatic embeddings of 2-colored trees (resp. 2-colored binary trees). Finally, we show that universal convex point sets with n points exist for 1-bend bichromatic point-set embeddings of 2-colored trees.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-36763-2_26
Classifications: G Algorithms and Complexity > G.490 Embeddings
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1318

Actions (login required)

View Item View Item