Drawing Colored Graphs with Constrained Vertex Positions and Few Bends per Edge

摘要

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 bends per edge.