Computational Complexity of the Vertex Cover Problem in the Class of Planar Triangulations

Abstract

We study the computational complexity of the vertex cover problem in the class of planar graphs (planar triangulations) admitting a plane representation whose faces are triangles. It is shown that the problem is strongly NP-hard in the class of 4-connected planar triangulations in which the degrees of vertices are of order O(log n), where n is the number of vertices, and in the class of plane 4-connected Delaunay triangulations based on the Minkowski triangular distance. A pair of vertices in such a triangulation is adjacent if and only if there is an equilateral triangle ∇(p, λ) with p ∈ R² and λ > 0 whose interior does not contain triangulation vertices and whose boundary contains this pair of vertices and only it, where ∇(p, λ) = p + λ∇ = {x ∈ R²: x = p + λa, a ∈ ∇}; here ∇ is the equilateral triangle with unit sides such that its barycenter is the origin and one of the vertices belongs to the negative y-axis. Keywords: computational complexity, Delaunay triangulation, Delaunay TD-triangulation.