Computational complexity of the vertex cover problem in the class of planar triangulations

K. S. Kobylkin

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 22 (2016) no. 3, pp. 153-159

Résumé

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.

Détail

Keywords: computational complexity
Mots-clés : Delaunay triangulation, Delaunay TD-triangulation.