Point-Set Embeddability of 2-Colored Trees - Archive ouverte HAL Access content directly
Conference Papers Year : 2013

Point-Set Embeddability of 2-Colored Trees

(1) , (2) , (3) , (4) , (5) , (6)
1
2
3
4
5
6

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.

Dates and versions

hal-01095415 , version 1 (15-12-2014)

Identifiers

Cite

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⟩

Collections

INRIA INRIA2
121 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More