Lemma 4.6 — simplifying maintains the planar non-alternating property
ProvedTRVB.PlanarNPC.lemma_4_6complexity-theorygraph-theoryp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let be a finite directed multigraph (loops and repeated arcs allowed) on a finite vertex set that is planar non-alternating, and let be an arc of with . Then the multigraph obtained by simplifying over is planar non-alternating.
Differences from the source:
- generalization: directed graph G → any finite vertex type V and arc list A : List (V × V), loops and repeated arcs allowed; reason: specializes to directed graphs; Theorem 4.7's proof applies the lemma to graphs that simplification has already given loops (INSIGHTS I1)
- encoding: edge (u, v) of G → (u, v) ∈ A together with u ≠ v; reason: contracting a loop is undefined; for a loopless G the condition is automatic
- encoding: planar non-alternating embedding (inward edges in one contiguous section at every vertex) → IsPlanarNonAlternating: a planar rotation system σ with at most one head end d at each vertex whose successor σ d is a tail end; reason: a combinatorial rendering of Definition 4.2 on the planar rotation system
- encoding: simplifying G over (u, v): the result has one new vertex instead of u and v → simplify A u v huv on the vertex type {x // x ≠ v}, the merged vertex represented by u; it keeps the arcs whose head is not v and whose tail is not u, with v renamed u; reason: the same multigraph up to naming the new vertex
- encoding: planar multigraph (has an embedding in the plane) → IsPlanarMG: a rotation system on the edge ends with #vertex orbits + #face orbits = #edges + 2·#components (genus 0 on every component); reason: Heffter–Edmonds–Ringel rotation principle and Euler's formula: equivalent for finite multigraphs with loops and parallel edges
Preamble
import Definitions.Def_TRVB_PlanarNPC_Digraph set_option autoImplicit false
Formal statement
namespace TRVB.PlanarNPC
/-- Lemma 4.6 (p. 11): simplifying maintains the planar non-alternating property. -/
theorem lemma_4_6 {V : Type} [Fintype V] [DecidableEq V] (A : List (V × V)) (u v : V)
(huv : u ≠ v) (hA : (u, v) ∈ A) (hpna : IsPlanarNonAlternating A) :
IsPlanarNonAlternating (simplify A u v huv) := by sorry
end TRVB.PlanarNPC
Source
Demaine & Rudoy, Tree-Residue Vertex-Breaking: a new tool for proving hardness, arXiv:1706.07900v3 (3 May 2018; SWAT 2018, doi:10.4230/LIPIcs.SWAT.2018.32), Lemma 4.6, p. 11 (PDF p. 11). Verbatim: 'Lemma 4.6. If (u, v) is an edge of planar non-alternating directed graph G, then simplifying G over (u, v) maintains the planar non-alternating property of G.' PDF SHA-256: d5f076af211e597d517c4365b4401ca0a6341590adb0a62be78489b9e737fcd7.
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.