Séminaire Lotharingien de Combinatoire, 86B.43 (2022), 12 pp.

Eran Nevo and Simion Tarabykin

Vertex Spanning Planar Laman Graphs in Triangulated Surfaces

Abstract. We prove that every triangulation of either of the torus, projective plane and Klein bottle, contains a vertex-spanning planar Laman graph as a subcomplex. Invoking a result of Király, we conclude that every 1-skeleton of a triangulation of a surface of nonnegative Euler characteristic has a rigid realization in the plane using at most 26 locations for the vertices.

Received: November 25, 2021. Accepted: March 4, 2022. Final version: April 1, 2022.

The following versions are available:

PDF (172 K)
TeX version