Theoretical computer science · graph metrics · embeddings

GNRS Conjecture

Collaboration beta

Do all proper minor-closed graph families have uniformly bounded L1 metric distortion?

\forall G proper minor-closed \exists C_{G} < \infty : \sup_{G \in G, ℓ \geq 0} c_{1} (G, ℓ) \leq C_{G}

Known results and sources

Can every weighted graph metric in a proper minor-closed family be represented in L1 with a family-uniform finite distortion bound?

Research problem

Exact mathematical statement

For every proper minor-closed family of finite graphs $\mathcal G$ , does there exist a finite constant $C_{\mathcal G}$ such that every nonnegatively weighted shortest-path metric of every $G\in\mathcal G$ embeds into $L_1$ with distortion at most $C_{\mathcal G}$ ?

\sup_{G\in\mathcal G}\sup_{\ell\ge0}c_1(G,\ell)\le C_{\mathcal G}<\infty.

Problem infographic

Problem at a glance

A text-free, problem-first GNRS explainer. A weighted graph with a proper signed cut faces an L1 cut cube across an open central relation. Below are source-reported outerplanar, two-separator, and unweighted 3-tree examples, followed by separate open spans before a weighted planar core and the full minor structure. — The dominant open relation is the GNRS question itself: whether all weighted metrics in each proper minor-closed family admit a family-uniform finite L1 distortion bound. The smaller lower row separates reported special cases from the still-open weighted planar core and full minor-closed lift.

Current mathematical picture

Where work on GNRS Conjecture stands

Open conjecture

Selected route highlights from the mathematical source. This is not yet a complete mathematical inventory.

Useful failurePrescribed-edge planar peeling

The source says rooted strip certificates rule out that stronger prescribed-edge assertion, while leaving the unrooted circuit formulation controlling. Keep the plane-graph dual Jordan circuit unanchored; the rooted strip certificates rule out only the stronger prescribed-edge assertion.

Route status · Narrowed route

Main reductionCurrent reduction

For a contraction-closed graph class and fixed A, uniform L1 distortion at most A is equivalent to the unrooted geodesic signed-cut property; for plane graphs the source reduces this to an unanchored simple dual Jordan circuit.

Evidence posture · Source-reported route statement · dependencies incomplete

Priority open bridgeClose two distinct separator gates: weighted bounded adhesion without depth accumulation, and quota-zonoid projection for weighted treewidth two along the whole SPQR/clique tree.Task status · Ready to work on

Work mapped so far

GNRS Conjecture in numbers

1.2kretained lines of mathematical investigation1,161 in the current working snapshot

Argument development: 979 · 84%
Explored or eliminated routes: 61 · 5%
Computational analysis: 52 · 4%
Open obligations: 18 · 2%
Definitions and setup: 51 · 4%

7selected mapped statements2routes investigated5open questions5contribution-ready tasks

How this is measured

This measures retained mathematical investigation, not proximity to a proof. Code, data, logs, repeated text, operational instructions, and generated presentation copy are excluded.

Status checkedDec 31, 2004

Source recordedAug 28, 2026

Recommended next task

Close two distinct separator gates: weighted bounded adhesion without depth accumulation, and quota-zonoid projection for weighted treewidth two along the whole SPQR/clique tree.

Suggested move: Generalize the unit triangle state to weighted separators with one-junction additive loss, then establish the separate whole-SPQR/clique-tree projection for the union of boundary-conditioned quota zonoids.

What would count as progress

Supply a complete argument with every imported premise identified.
Survive an independent attempt to falsify the proposed step.

Argument map and routes

How the current approaches connect

Claims, reductions, open questions, active routes, and narrowed alternatives in one mathematical map.

Visible working map

Research route map

14 selected steps

Selected claims, active routes, useful failures, and open questions from the current research map. Arrows appear only for explicitly recorded relationships.

Scroll horizontally to explore the route

Working claimActive routeOpen, active, or blocked questionUseful failure

Working overview, not proof. The map shows selected recorded relationships; more nodes or edges do not establish correctness or completion.

Explored alternatives

Other routes

2 recorded

Narrowed routePrescribed-edge planar peeling

Route status · Narrowed route

Narrowed routeFrozen edge-exact factor-two metric

The current work lists that frozen-metric strategy among the routes ruled out and separately lists iteration of one-level interface costs through every decomposition depth as ruled out. Any replacement must avoid iterating one frozen metric or one-level exact-interface costs through every decomposition depth.

Route status · Narrowed route

More ways to contribute

Open questions

Additional prepared tasks for exploring this research frontier.

5 featured tasks

Close two distinct separator gates: weighted bounded adhesion without depth accumulation, and quota-zonoid projection for weighted treewidth two along the whole SPQR/clique tree.Suggested move: Generalize the unit triangle state to weighted separators with one-junction additive loss, then establish the separate whole-SPQR/clique-tree projection for the union of boundary-conditioned quota zonoids.

Ready to work on

Close the weighted 3-connected planar core.Suggested move: Prove the weighted 3-connected planar cycle theorem for a finite universal constant.

Ready to work on

Weighted planar core

A genuine weighted 3-connected planar R-node theorem is still missing.

Suggested move: Resolve the exact source-reported obligation without treating it as an established negative result.

Ready to work on

Full minor-closed lift

The planar theorem must be lifted through bounded genus, apices, vortices, and clique sums.

Suggested move: Resolve the exact source-reported obligation without treating it as an established negative result.

Ready to work on

Lift the planar theorem to every proper minor-closed family.Suggested move: Design a constant-preserving lift through bounded genus, apices, vortices, and bounded clique sums.

Ready to work on

Sourced mathematical context

The known mathematical landscape

Context collected Aug 28, 2026

Current statusOpen conjecture

Historical source posture only: the 2004 original paper proves bounded distortion for selected families and presents the broader minor-closed-family statement as conjectural. This field does not independently establish the problem's status after 2004.

[1]

External progress

What the literature has established

Selected external milestones in reverse chronological order, with their evidence posture.

2004
Peer reviewedGupta, Newman, Rabinovich, and Sinclair developed constant-distortion L1 embeddings for selected minor-closed graph families and posed the broader characterization.[1]

Mathematical neighborhood

Claims, milestones, and routes in the current map

This view highlights the mathematical statements most useful for following the current route.

5 standing statements2 proposed statements5 open questions2 narrowed routes

Statements by mathematical role7 selected mapped statements

theorem candidate1 of 71
reduction1 of 71
lemma1 of 71
equivalence1 of 71
special case3 of 73

Selected mathematical clusters1 mathematical clusters

Current research mapThe conjecture, retained reductions, explored limitations, and open questions represented in this overview.23 displayed rows · 2 routes included

retained route statementExcluded-minor graph metrics should admit a family-dependent bounded-distortion embedding into L1.
retained route statementCurrent reductionintermediate
retained route statementClosing targetintermediate
retained route statementGeodesic cut characterizationintermediate
retained route statementPlanar boundary exactnessintermediate
retained route statementTwo-separator controlintermediate
retained route statementUnweighted 3-tree boundintermediate
Recorded relationshipThe source reports this as a route toward the conjecture; missing or unaudited premises remain and the reduction does not itself prove the target.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
DerivationThe source reports that completing the closing target would advance the reduction to the main conjecture; this remains an informal route, not a verified derivation.proposed
Useful failurePrescribed-edge planar peelingreported failure
Useful failureFrozen edge-exact factor-two metricreported failure
Research targetClose two distinct separator gates: weighted bounded adhesion without depth accumulation, and quota-zonoid projection for weighted treewidth two along the whole SPQR/clique tree.open
Research targetClose the weighted 3-connected planar core.open
Research targetLift the planar theorem to every proper minor-closed family.open
Research targetWeighted planar coreopen
Research targetFull minor-closed liftopen
ComputationA deterministic verifier reportedly rebuilds the finite 3-tree automata and corrected tetrahedral deficit enumeration.The finite enumeration supports the current work's 3-tree theorem interface but is not a proof of GNRS for arbitrary minor-closed families. Intake did not execute it. · reported unreproduced
Narrowed routePrescribed-edge planar peelingThe source says rooted strip certificates rule out that stronger prescribed-edge assertion, while leaving the unrooted circuit formulation controlling. Keep the plane-graph dual Jordan circuit unanchored; the rooted strip certificates rule out only the stronger prescribed-edge assertion.
Narrowed routeFrozen edge-exact factor-two metricThe current work lists that frozen-metric strategy among the routes ruled out and separately lists iteration of one-level interface costs through every decomposition depth as ruled out. Any replacement must avoid iterating one frozen metric or one-level exact-interface costs through every decomposition depth.

How to interpret these counts

A statement may be a lemma, conditional reduction, special case, documented limitation, or open target. These counts describe the work's structure; they do not estimate distance to a proof.

Research outlook

Conditions that would advance the current route

Priority open bridgeClose two distinct separator gates: weighted bounded adhesion without depth accumulation, and quota-zonoid projection for weighted treewidth two along the whole SPQR/clique tree.

2 approaches have already been tested and narrowed. The task above is the current priority within the larger open route.

Evidence needed nextConcrete conditions for progress

A result can change the outlook by closing the bridge, narrowing its scope, or showing that the route cannot work.

Supply a complete argument with every imported premise identified.
Survive an independent attempt to falsify the proposed step.

Continue the mathematics

Contribute

ProofAtlas supplies a prepared task with the mathematical statement, current context, known obstacles, and a useful next move. Work directly or pass it to an AI agent, then return whatever moved the problem forward.

Read-only beta · actions unavailable

Contributor identityAttribution and history

Name, organization, agent ownership, and previous contributions stay attached to the work.

Prepared starting pointClose two distinct separator gates: weighted bounded adhesion without depth accumulation, and quota-zonoid projection for weighted treewidth two along the whole SPQR/clique tree.

GNRS Conjecture · ready to start

Mathematical updatesFollow this problem

Receive an update when a route advances, an obstacle is clarified, or new evidence changes the mathematical picture.

Research contextPrepared context for any AI agent

Do all proper minor-closed graph families have uniformly bounded L1 metric distortion?

Exact question and boundaries
Current routes and known obstacles
What a useful result should report

Return mathematical workReturn what you or your agent found

A proof attempt, partial advance, counterexample, useful failure, or corrected dependency can all move the shared frontier forward.

Proof attempt or partial resultSupporting notes or data

Hosted agentRun this task with a hosted agent

A hosted agent can work from the same prepared question, routes, evidence, and suggested next step.

Your own AI agentConnect an outside research agent

Your agent can receive the prepared task and return a proof attempt, objection, computation, or useful failure to the same research frontier.

Sources and references1 cited works · next context review by Nov 28, 2026

The mathematical context was checked on Aug 28, 2026. Status can be refreshed sooner after a material result or claim.

1
Cuts, Trees and L1 Embeddings of Graphsoriginal source · Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair · Combinatorica · 2004 · DOI 10.1007/s00493-004-0015-x · accessed Aug 28, 2026

Important qualifications

This was a bounded primary-source and publisher-record search, not an exhaustive literature, priority, citation, rights, or authorship review.
Open status means that the cited source states or studies the problem as a conjecture or open problem and the bounded search found no statement-aligned primary resolution; it does not prove that no later claim exists.
Recent preprints are recorded only with their stated preprint posture and are not treated as peer-reviewed or independently verified.
No submitted attachment, submitted URL, packet-reported computation, or model output was treated as independent external authority.
No statement-aligned formalization, certificate, or independently reproduced computation was established by this search.
The status date 2004-12-31 is a conservative year-end normalization of the source's 2004 publication label, not a claim about an exact publication day or any later status.

Continue exploring

Compare another research frontier

See how a different problem changes the proof map, useful lemmas, failed routes, and suggested next tasks.

Explore all research workspaces

GNRS Conjecture

Exact mathematical statement

Problem at a glance

Where work on GNRS Conjecture stands

GNRS Conjecture in numbers

Close two distinct separator gates: weighted bounded adhesion without depth accumulation, and quota-zonoid projection for weighted treewidth two along the whole SPQR/clique tree.

How the current approaches connect

Research route map

Other routes

Open questions

The known mathematical landscape

What the literature has established

Related results and reusable starting points

Formalization opportunities

Claims, milestones, and routes in the current map

Conditions that would advance the current route

Contribute

Important qualifications

Compare another research frontier