Maximal drawable extension on the same vertices
ProvedWilliamsonShmoys.planar_edge_count_maximal_extension_eeac03ef_36e6_44d1_be88_71ee042c1f55approximation-algorithmsplanar-graphstreewidth
Extend any drawable graph on at least three vertices to a drawable graph on the same vertices that contains it, has at least as many edges, and is maximal among drawable supergraphs. This handles disconnected inputs. An independent proof route is to maximize edge count among the finite set of drawable supergraphs of L; any drawable graph containing that maximizer also contains L, so the maximum gives the stated maximality.
Preamble
import Mathlib import Definitions.Def_WilliamsonShmoys_PlanarDrawingOn
Formal statement
theorem WilliamsonShmoys.planar_edge_count_maximal_extension_eeac03ef_36e6_44d1_be88_71ee042c1f55 {V : Type} [Fintype V] [LinearOrder V] (L : SimpleGraph V) (hV : 3 ≤ Fintype.card V) (hL : WilliamsonShmoys.HasPlanarDrawingOn L) : ∃ M : SimpleGraph V, L.edgeSet.ncard ≤ M.edgeSet.ncard ∧ L ≤ M ∧ WilliamsonShmoys.HasPlanarDrawingOn M ∧ (∀ N : SimpleGraph V, M ≤ N → WilliamsonShmoys.HasPlanarDrawingOn N → N ≤ M) := 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).