A New Algorithm for Embedding Plane Graphs at Fixed Vertex Locations

Abstract

We show that a plane graph can be embedded with its vertices at pre-assigned (fixed) locations in the plane and at most $2.5n + 1$ bends per edge.  This improves and simplifies a classic result by Pach and Wenger.  The proof extends to grid embeddings, orthogonal embeddings, and minimum length embeddings.