Minimum Edge-Outerplanar Embeddings are Polynomial-Time Computable

Abstract

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.