NP-Completeness Results for Minimum Planar Spanners

this paper, we prove the NP--hardness of finding minimum t--spanners for planar weighted graphs and digraphs if t 3, and for planar unweighted graphs and digraphs if t 5. We thus extend results on that problem to the interesting case where the instances are known to be planar. We also introduce the related problem of finding minimum planar t--spanners and conclude its NP--hardness for similar fixed values of t