Hamiltonicity, book embeddability, and point-set embeddability of planar graphs are strictly related concepts. We exploit the interplay between these notions to describe colored sets of points and to design polynomial-time algorithms to embed k-colored planar graphs on these sets such that the resulting drawings have O(k) bends per edge.
Drawing Colored Graphs with Constrained Vertex Positions and Few Bends per Edge
DI GIACOMO, Emilio;LIOTTA, Giuseppe;
2008
Abstract
Hamiltonicity, book embeddability, and point-set embeddability of planar graphs are strictly related concepts. We exploit the interplay between these notions to describe colored sets of points and to design polynomial-time algorithms to embed k-colored planar graphs on these sets such that the resulting drawings have O(k) bends per edge.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.
