Geodesic
Computational complexity of the vertex cover problem in the class of planar triangulations
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 22 (2016) no. 3, pp. 153-159 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

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.
Keywords: computational complexity
Mots-clés : Delaunay triangulation, Delaunay TD-triangulation. 
@article{TIMM_2016_22_3_a14,
     author = {K. S. Kobylkin},
     title = {Computational complexity of the vertex cover problem in the class of planar triangulations},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {153--159},
     year = {2016},
     volume = {22},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2016_22_3_a14/}
}
TY  - JOUR
AU  - K. S. Kobylkin
TI  - Computational complexity of the vertex cover problem in the class of planar triangulations
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2016
SP  - 153
EP  - 159
VL  - 22
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/TIMM_2016_22_3_a14/
LA  - ru
ID  - TIMM_2016_22_3_a14
ER  - 
%0 Journal Article
%A K. S. Kobylkin
%T Computational complexity of the vertex cover problem in the class of planar triangulations
%J Trudy Instituta matematiki i mehaniki
%D 2016
%P 153-159
%V 22
%N 3
%U http://geodesic.mathdoc.fr/item/TIMM_2016_22_3_a14/
%G ru
%F TIMM_2016_22_3_a14
K. S. Kobylkin. Computational complexity of the vertex cover problem in the class of planar triangulations. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 22 (2016) no. 3, pp. 153-159. http://geodesic.mathdoc.fr/item/TIMM_2016_22_3_a14/

[1] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982, 416 pp. | MR

[2] Alekseev V.E., Malyshev D.S., “Planar graph classes with the independent set problem solvable in polynomial time”, J. Appl. Ind. Math., 3:1 (2009), 1–4 | DOI | MR

[3] Biniaz A., Maheshwari A., Smid M., “Higher-order triangular-distance Delaunay graphs: graph-theoretical properties”, Comput. Geometry, 48:9 (2015), 646–660 | DOI | MR | Zbl

[4] Bodlaender H.L., “A partial k-arboretum of graphs with bounded treewidth”, Theoret. Comput. Sci., 209:1–2 (1998), 1–45 | DOI | MR | Zbl

[5] Brause C., Le N.C., Schiermeyer I., “The maximum independent set problem in subclasses of subcubic graphs”, Discrete Math., 338:10 (2015), 1766–1778 | DOI | MR | Zbl

[6] N. Bonichon, C. Gavoille, N. Hanusse, D. Ilcinkas, “Connections between $\theta$-graphs, Delaunay triangulations and orthogonal surfaces”, Graph Theoretic Concepts in Computer Science, Proc. Workshop, Lecture Notes in Computer Science, 6410, Springer, Berlin, 2010, 266–278 | DOI | MR | Zbl

[7] Das G., Goodrich M.T., “On the complexity of optimization problems for 3-dimensional convex polyhedra and decision trees”, Comput. Geometry, 8:3 (1997), 123–137 | DOI | MR | Zbl

[8] Diestel R., Graph theory, Springer-Verlag, Heidelberg, 2010, 451 pp. | MR

[9] Dillencourt M.B., “Realizability of Delaunay triangulations”, Inform. Process. Lett., 33:6 (1990), 283–287 | DOI | MR | Zbl

[10] Dillencourt M.B., Smith W.D., “Graph-theoretical conditions for inscribability and Delaunay realizability”, Discrete Math., 161:1–3 (1996), 63–77 | DOI | MR | Zbl

[11] Dirac G.A., “On rigid circuit graphs”, Abh. Math. Sem. Univ. Hamburg, 25:1 (1961), 71–76 | DOI | MR | Zbl

[12] Fleischner H., Sabidussi G., Sarvanov I., “Maximum independent sets in 3- and 4-regular Hamiltonian graphs”, Discrete Math., 310:20 (2010), 2742–2749 | DOI | MR | Zbl

[13] Gavril F., “Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph”, SIAM J. Comput., 1:2 (1972), 180–187 | DOI | MR | Zbl

[14] Kaminski M., Lozin V.V., Milanic M., “Recent developments on graphs of bounded clique-width”, Discrete Appl. Math., 157:12 (2009), 2747–2761 | DOI | MR | Zbl

[15] Malyshev D.S., “Classes of subcubic planar graphs for which the independent set problem is polynomially solvable”, J. Appl. Ind. Math., 7:4 (2013), 537–548 | DOI | MR | Zbl

[16] Mohar B., “Face covers and the genus problem for apex graphs”, J. Combin. Theory. Ser.B, 82:1 (2001), 102–117 | DOI | MR | Zbl

[17] Narasimhan G., Smid M., Geometric spanner networks, Cambridge Univ. Press, Cambridge; N Y; Melbourne, 2007, 500 pp. | MR | Zbl

[18] P. Bose, V. Dujmovic, F. Hurtado, J. Iacono, S. Langerman, H. Meijer, V. Sacristan, M. Saumell, D. Wood, “Proximity graphs: $E, \delta, \Delta, \chi$ and $\omega$”, Internat. J. Comput. Geom. Appl., 22:5 (2012), 439–470 | DOI | MR

[19] Rote G., “Strictly convex drawings of planar graphs”, Proc. of the sixteenth annual ACM-SIAM symposium on Discrete algorithms (electronic), ACM, N. Y., 2005, 728–734 | MR | Zbl

[20] T.K. Dey, M.B. Dillencourt, S.K. Ghosh, J.M. Cahill, “Triangulating with high connectivity”, Comput. Geometry, 8:1 (1997), 39–56 | DOI | MR | Zbl