Colored Point-set Embeddings of Acyclic Graphs

Abstract

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 $\Omega (n^{\frac{1}{3}})$ bends in the worst case. The lower bound holds even when the function that maps vertices to points is not a bijection but it is defined by a 3-coloring. In contrast, a constant number of bends per edge can be obtained for 3-colored paths and for 3-colored caterpillars whose leaves all have the same color. Such results answer to a long standing open problem.

Appears in the Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD 2017)