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.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/hal-01095415
Contributor : Marc Glisse <>
Submitted on : Monday, December 15, 2014 - 3:39:45 PM
Last modification on : Friday, September 20, 2019 - 4:56:35 PM

Links full text

Identifiers

Collections

Citation

Fabrizio Frati, Marc Glisse, Bill Lenhart, Giuseppe Liotta, Tamara Mchedlidze, et al.. Point-Set Embeddability of 2-Colored Trees. Graph Drawing, 2012, Redmond, United States. pp.12, ⟨10.1007/978-3-642-36763-2_26⟩. ⟨hal-01095415⟩

Share

Metrics

Record views

186