2-colored point-set embeddability of the outerplanar graphs

Abstrakt

Given a planar graph and a set of points in a plane, we want to embed the vertices into the points such that each edge is partially straight line with at most d bends. We want to bound the constant d for various families of plane graphs.

More specifically, we show that any outerplanar graph can be embedded into two-colour point-set using at most 4 bends per edge.

Klíčová slova

• partiallý straight-line embedding
• outerplanar graph