Four-connected triangulations of planar point sets

Ajit Arvind Diwan, Subir Kumar Ghosh, Bodhayan Roy

In this paper, we consider the problem of determining in polynomial time whether a given planar point set $P$ of $n$ points admits 4-connected triangulation. We propose a necessary…