2017/08/30 by Di Giacomo, Emilio, Gasieniec, Leszek, Liotta, Giuseppe +1 · 1 citation
#Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1708.09167
We show that any planar drawing of a forest of three stars whose vertices are constrained to be at fixed vertex locations may require Ω(n^(2)/(3)) edges each having Ω(n^(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.