Minimum edge-outerplanarity planar embeddings
Follow the latest progress by email.
Given a finite loopless planar graph, possibly with parallel edges, find a planar embedding minimizing edge-outerplanarity, the number of edge-peeling layers.
Why it matters and what counts as progress
Why it matters: It asks whether optimizing this embedding-dependent depth can be done in polynomial time rather than only computing depth for a chosen embedding.
What counts as progress: An algorithm returning an embedding of minimum edge-peeling depth with polynomial runtime, including disconnected structure and parallel edges as allowed.
How the problem developed
- 2009 · Open problem [1]
Andreas Bentz Posed the problem of computing the minimum edge-outerplanarity over planar embeddings of a graph.
- 9 Jul 2026 · Algorithm [1]
Hantao Yu, with GPT-5.5 Pro credited for the initial proof Gave a polynomial-time algorithm for computing the minimum edge-outerplanarity of a planar graph.
AI contribution
Minimum Edge-Outerplanar Embeddings are Polynomial-Time Computable
A polynomial-time algorithm finds a planar embedding of minimum edge-outerplanarity for every finite loopless planar graph, including graphs with parallel edges. It reduces edge-peeling depth to minimum face-depth of an auxiliary planar graph.
Sources
Website timeline
Publication dates and editorial changes.
AI-led proof gives a minimum edge-outerplanar embedding algorithm