CCJul 9
Minimum Edge-Outerplanar Embeddings are Polynomial-Time Computable
arXiv:2607.081109.6
Predicted impact top 31% in CC · last 90 daysOriginality Highly original
AI Analysis
Solves a long-standing open problem in graph theory for researchers studying planar graph embeddings.
The paper resolves the open problem of computing the minimum edge-outerplanarity of a planar graph in polynomial time, providing a polynomial-time algorithm.
We prove that the minimum edge-outerplanarity of a planar graph can be computed in polynomial time, resolving an open problem of Bentz (2009). The proof was initially produced by GPT~5.5 Pro and then verified and polished manually.