Embedding a triangular graph within a given boundary (Q654561)

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? An algorithm which decides this problem and produces such an embedding if it exists, or reject the input in case no valid embedding exists is described in this article. Experimental results demonstrate the effectiveness of the introduced algorithm.