Point-Set Embeddability of 2-Colored Trees

Abstract : 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 $\cal NP$-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.
Type de document :
Communication dans un congrès
Walter Didimo and Maurizio Patrignani. Graph Drawing, 2012, Redmond, United States. Springer Berlin Heidelberg, Lecture Notes in Computer Science, 7704, pp.12, 2013, GD'12 Proceedings of the 20th international conference on Graph Drawing. 〈10.1007/978-3-642-36763-2_26〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01095415
Contributeur : Marc Glisse <>
Soumis le : lundi 15 décembre 2014 - 15:39:45
Dernière modification le : jeudi 11 janvier 2018 - 16:44:55

Identifiants

Collections

Citation

Fabrizio Frati, Marc Glisse, Bill Lenhart, Giuseppe Liotta, Tamara Mchedlidze, et al.. Point-Set Embeddability of 2-Colored Trees. Walter Didimo and Maurizio Patrignani. Graph Drawing, 2012, Redmond, United States. Springer Berlin Heidelberg, Lecture Notes in Computer Science, 7704, pp.12, 2013, GD'12 Proceedings of the 20th international conference on Graph Drawing. 〈10.1007/978-3-642-36763-2_26〉. 〈hal-01095415〉

Partager

Métriques

Consultations de la notice

84