Colored Point-set Embeddings of Acyclic Graphs

Emilio Di Giacomo, Leszek Gasieniec, Giuseppe Liotta +1

We show that any planar drawing of a forest of three stars whose vertices are constrained to be at fixed vertex locations may require $\Omega (n^{\frac{2}{3}})$ edges each having $Ω(n^\fra…