Minimum Edge-Outerplanar Embeddings are Polynomial-Time Computable

Jul 16, 2026

The paper proves that the minimum edge-outerplanarity value of a planar graph can be computed in polynomial time, resolving an open problem posed by Bentz (2009). It formulates k-edge-outerplanarity via an edge-peeling process that removes edges on successive outer faces. The main theorem guarantees an embedding achieving the optimum minimum edge-outerplanarity for every finite loopless planar graph, and the approach reduces the task to computing a minimum face-depth embedding using known polynomial-time results.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages10

Reading Time25 min

Abstract

Introduction

Statement on AI use

Preliminaries

Edge peeling in a fixed embedding

Face reachability after edge deletions

arXiv :2607 .08 1 10v 1 [ cs .CC] 9 Jul 2026 Minimum Edge-Outerplanar Embeddings are Polynomial-Time Computable Hantao Yu Columbia University [hantao. yu@columbia. edu](hantao. yu@columbia. edu) 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. 1 Introduction A plane embedding of a graph is called k-edge-outerplanar if the following edge-peeling process deletes all edges in at most k rounds: in each round, delete every edge lying on the outer face of the current embedding. The associated optimization problem asks for a planar embedding minimizing the number of edge-peeling rounds. For the vertex analogue, namely ordinary k-outerplanarity, minimum-k embeddings are known tobe computable in polynomial time [3] . Bentz introduced k-edge-outerplanar graphs in the study of edge-disjoint paths and multicut problems, and asked whether the analogous statement holds fork-edge-outerplanarity [2] . We answer this question affirmatively for loopless planar graphs. Theorem 1.1 (Main theorem) . For every finite loopless planar graph G, a planar embedding of G with minimum possible edge-outerplanarity can be found in polynomial time. Remark 1.2. The proof below allows parallel edges. Thus it applies to all finite loopless planar multigraphs, and in particular to all finite simple planar graphs. We do not discuss loops. We reduce the problem to the known polynomial-time problem of computing an embedding of minimum face-depth. The depth of a plane embedding is the maximum distance, in the faceadjacency graph, from the outer face to any other face. Bienstock and Monma studied polynomialtime algorithms for minimizing several such embedding distance measures [3] . Angelini, Di Battista, and Patrignani later gave an O(n4 )-time algorithm for computing a minimum-depth embedding of an n-vertex planar graph [1] . 1.1 Statement on AI use The proof is generated using the agentic pipeline from the pipeline-math project 1 . The pipeline involves the use of GPT 5.5 Pro and Claude Opus 4.8, where GPT 5.5 Pro acts as a solver and Claude Opus 4.8 acts as a verifier. The proof is then verified by the authors, and thus the authors are solely responsible for the correctness of the proof. 1 [https://github.com/Pengbinghui/pipeline-math.git](https://github.com/Pengbinghui/pipeline-math.git) 2 Preliminaries Throughout this paper, we assume that all graphs are finite. Unless stated otherwise, graphs are allowed to have parallel edges but have no loops. Let Γ be a plane embedding of a graph G. Let F(Γ) be the set of faces of Γ, and let f∞ be the outer face. The face-adjacency graph of Γ, denoted DΓ, is the graph whose vertices are the faces of Γ, with an edge between two faces whenever they share a primal edge. We also define FΓ(e) tobe the set of faces in F(Γ) that are incident to e. If a primal edge e is a bridge, then it is incident with the same face on both sides; in this case FΓ(e) has one element, and the bridge contributes only a loop in the face-adjacency graph, and such loops are ignored for distances. For a face f ∈ F(Γ), define dΓ (f) := distDΓ (f∞ , f) . The depth of the embedding Γ is depth(Γ) := max dΓ (f) . f∈F(Γ) Including the outer face in this maximum is harmless, since dΓ (f∞ ) = 0 . We note that the face-adjacency graph of any plane graph, connected or not, is connected: a generic arc from an interior point of a face f to a point of f∞ , chosen transversal to the edges and avoiding the vertices, crosses only edges and thus traces a walk from f to f∞ in DΓ . Hence dΓ (f) is finite for every face f, and the edge-peeling process deletes every edge after finitely many rounds. For an edge e ∈ E (G), let λΓ (e) be the round in which e is deleted by the edge-peeling process. Thus an edge lying on the original ou

FAQs

What does k-edge-outerplanarity mean for a planar graph embedding?

A plane embedding is k-edge-outerplanar if deleting every edge on the outer face in each round removes all edges within at most k rounds. The optimization seeks an embedding that minimizes these peeling rounds.

What is the main theorem established in the paper?

For every finite loopless planar graph G, there exists a planar embedding with minimum possible edge-outerplanarity, and such an embedding can be found in polynomial time.

How is the edge-outerplanarity problem reduced for computation?

The paper reduces the problem to computing a minimum face-depth embedding. Embedding depth is defined as the maximum face-adjacency distance from the outer face to any other face, and a known polynomial-time algorithm for minimum-depth embeddings is used.

Jul 16, 2026

Upload by Theodore