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(\log n)$, 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 $\nabla(p,\lambda)$ with $p\in\mathbb{R}^2$ and $\lambda>0$ whose interior does not contain triangulation vertices and whose boundary contains this pair of vertices and only it, where $\nabla(p,\lambda)=p+\lambda\nabla=\{x\in\mathbb{R}^2\colon x=p+\lambda a,a\in\nabla\}$; here, $\nabla$ 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