Finding k-edge-outerplanar graph embeddings

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

Let $G$ be a finite planar graph. For a plane embedding $\mathcal E$, remove simultaneously all edges incident with the unbounded face, retain the inherited embedding, and repeat until no edges remain. Write $p(\mathcal E)$ for the number of rounds and $p(G)=\min_{\mathcal E}p(\mathcal E)$; an edgeless graph has $p(G)=0$.

Statement recorded in the supplied source.

Is there a polynomial-time algorithm which, given $G$, constructs a plane embedding $\mathcal E$ satisfying $p(\mathcal E)=p(G)$? [S2]

Short English statement

Can an embedding with the minimum number of edge-peeling layers be found in polynomial time?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3113 (OPG-37218). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Finding k-edge-outerplanar graph embeddings, original node 37218, statement and mathematical discussion. https://www.openproblemgarden.org/op/finding_k_edge_outerplanar_graph_embeddings.