Every finite simple planar graph has a triangulated planar completion
ProvedWilliamsonShmoys.planar_triangulated_completion_existsapproximation-algorithmsplanar-graphstreewidth
For every finite simple graph with at least three vertices and a crossing-free drawing as defined by HasPlanarDrawingOn, there is a planar supergraph on the same vertex type whose faces are triangles and whose edge count is exactly three times the number of vertices minus six. One proof route joins drawing components, adds noncrossing diagonals until all faces are triangular, then applies Euler’s formula and counts face-edge incidences. The vertex-count hypothesis is retained for the triangulation count.
Preamble
import Mathlib import Definitions.Def_WilliamsonShmoys_PlanarDrawingOn set_option autoImplicit false
Formal statement
theorem WilliamsonShmoys.planar_triangulated_completion_exists
{V : Type} [Fintype V] [LinearOrder V]
(L : SimpleGraph V)
(hL : WilliamsonShmoys.HasPlanarDrawingOn L)
(hV : 3 ≤ Fintype.card V) :
∃ M : SimpleGraph V,
L ≤ M ∧
WilliamsonShmoys.HasPlanarDrawingOn M ∧
M.edgeSet.ncard = 3 * Fintype.card V - 6 := by
sorrySource
David P. Williamson and David B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011, author electronic manuscript, Section 10.2, proof of Theorem 10.11, pp. 270-272. https://doi.org/10.1017/CBO9780511921735. Bounded tree-width of the pieces: Robertson–Seymour (planar graphs of radius r have tree-width at most 3r+1) / Bodlaender (k-outerplanar graphs have tree-width at most 3k-1).