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.
Colored point-set embeddings of acyclic graphs
Di Giacomo, Emilio
;Liotta, Giuseppe;Navarra, Alfredo
2018
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 Ω(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.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
