Abstract:
We study the computational complexity of the vertex cover problem in the class of planar graphs (planar triangulations) admitting a planar 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 all vertices are of order O(logn), where n is the number of vertices, and in the class of planar 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∈R2 and λ>0 whose interior does not contain triangulation vertices and whose boundary contains this pair of vertices and only it, where ∇(p,λ)=p+λ∇={x∈R2: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.
Citation:
K. S. Kobylkin, “Computational complexity of the vertex cover problem in the class of planar triangulations”, Trudy Inst. Mat. i Mekh. UrO RAN, 22, no. 3, 2016, 153–159; Proc. Steklov Inst. Math. (Suppl.), 299, suppl. 1 (2017), 106–112