Recognition of Triangulation Duals of Simple Polygons With and Without Holes

Martin Derka, Alejandro López-Ortiz, Daniela Maftuleac

We investigate the problem of determining if a given graph corresponds to the dual of a triangulation of a simple polygon. This is a graph recognition problem, where in our particu…