Embedding a triangular graph within a given boundary

Given a 3-vertex-connected triangular planar graph and an embedding of its boundary vertices, can the interior vertices be embedded to form a valid triangulation? We describe an algorithm which decides this problem and produces such an embedding if it exists.

► We present an algorithm for embedding a triangular graph within a given boundary.
► The algorithm will decide whether such embedding exists, and produce one if it does.
► The algorithm is extended to improve the quality of the resulting triangulation.