Minimum Edge-Outerplanar Embedding

Precise statement

Can the minimum edge-outerplanarity of a finite loopless planar graph, minimized over all planar embeddings, be computed in polynomial time? Asked by Bentz in 2009.

The source statement is reproduced for indexing with attribution. Mathematical correctness requires domain-expert or mechanical review. VibeMath has not independently audited statement fidelity, correctness, priority, or novelty.

What AI did

GPT-5.5 Pro

The reduction to computing an embedding of minimum face-depth was initially produced by GPT-5.5 Pro, then verified and polished manually by the author.

Provider: OpenAI · Prompt public: unknown · Independence: unknown

Verification boundary

unreviewed

Author-checked and polished arXiv preprint. Not yet peer-reviewed.

Correctness: unknown · statement fidelity: unaudited · peer review: none

Timeline

1. 2026-07-09

   arXiv:2607.08110 - Minimum edge-outerplanar embeddings are polynomial-time computable

   VibeMathed reports this item as resolved. VibeMath preserves that report as a source assertion and has not independently authored a plain-language mathematical explanation.

Known method families

argument (source-reported)

Source-reported tools: argument.

Independent: unknown · difference confidence: 0

What remains uncertain

VibeMath has not independently audited the mathematical statement, proof, or novelty claim.

• VibeMath has not independently verified the mathematical claim.
• AI-attempt independence and training-data exposure are unknown unless explicitly documented.
• VibeMath has not independently audited the mathematical statement, proof, or novelty claim.