Determining unit distance graphs with coordinates in $\mathbb{Z}^2$ is NP-complete

Eric Binnendyk

arxiv: 2510.15002 · v3 · pith:ISVAFXBLnew · submitted 2025-10-16 · 💻 cs.CC

Determining unit distance graphs with coordinates in mathbb{Z}² is NP-complete

Eric Binnendyk This is my paper

Pith reviewed 2026-05-25 07:36 UTC · model grok-4.3

classification 💻 cs.CC

keywords unit-distance graphsNP-completenessinteger latticegraph realizationNA3SAT reductionlogic enginecomputational geometry

0 comments

The pith

Deciding whether a graph can be realized with unit distances on integer coordinates is NP-complete.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that recognizing whether a given graph can be placed with vertices at points of the integer lattice Z^2 and every edge exactly length one is an NP-complete problem. It establishes this by reducing from NA3SAT: for any formula of that satisfiability problem, a graph is built whose unit-distance realization in Z^2 exists exactly when the formula is satisfiable. The construction uses an adapted logic engine whose gadgets enforce the necessary distances and coordinate constraints. A reader would care because the result places a concrete geometric embedding task in the same hardness class as logical satisfiability, ruling out efficient algorithms unless P equals NP.

Core claim

The problem of determining whether a graph G can be realized as a unit-distance graph in Z^2 is NP-complete. This is shown by implementing Eades and Whitesides' logic engine in this setting and constructing a graph that is realizable if and only if an arbitrary NA3SAT formula is satisfiable.

What carries the argument

An adaptation of the Eades and Whitesides logic engine whose gadgets enforce unit distances and integer coordinates in the reduction from NA3SAT.

If this is right

No polynomial-time algorithm exists for the recognition problem unless P equals NP.
The reduction encodes logical satisfiability directly through distance and coordinate constraints on the lattice.
The same technique applies to showing hardness for other discrete geometric realization problems.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The hardness result suggests that many exact geometric constraint problems on grids inherit the same intractability.
Similar gadget constructions could be tested on other lattices or distance sets to map out the boundary between tractable and intractable cases.
Practical embedding tasks in grid-based networks or sensor placement would need to account for this worst-case complexity.

Load-bearing premise

The adapted gadgets correctly enforce unit distances and integer coordinates without permitting unintended realizations that would violate the if-and-only-if correspondence with satisfiability.

What would settle it

A polynomial-time algorithm that decides unit-distance realizability in Z^2 for arbitrary graphs, or an explicit counterexample graph constructed from an unsatisfiable NA3SAT instance that still admits a unit-distance embedding in Z^2.

read the original abstract

The problem of determining whether a graph $G$ can be realized as a unit-distance graph in $\mathbb{Z}^2$ is NP-complete. As far as we can tell, a proof of this result has never been written up. We prove NP-completeness of this problem by implementing Eades and Whitesides' logic engine in this setting, and construct a graph that is realizable if and only if an arbitrary NA3SAT formula is satisfiable.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper writes up the first formal NP-completeness proof for unit-distance realization on Z^2 by adapting the logic engine, but the gadget details are the part that needs checking.

read the letter

The main takeaway is that this paper writes up a proof that deciding whether a graph is a unit distance graph in the integer lattice is NP-complete. They adapt the Eades-Whitesides logic engine to reduce from NA3SAT in this discrete setting. It does a service by putting the result on paper, since the abstract notes it hadn't been formally written up. The approach follows a standard template for these problems, which is appropriate here. The weak point is the adaptation itself. On Z^2, unit distances are restricted to the four cardinal directions, so the gadgets from the continuous case won't transfer directly. The paper needs to define new gadgets and prove that their possible placements on the grid exactly simulate the logic without allowing extra configurations that could satisfy the graph without satisfying the formula. The abstract gives no such details, so the soundness rests on whether those constructions are correct and exhaustive. If the full text has the gadget diagrams and case checks, that would be fine; otherwise it's a gap. The rest of the paper seems to stick to the known reduction without adding free parameters or circular arguments. This is for specialists in geometric complexity. A reader working on similar realization problems would find it relevant once the gadgets are verified. It should go to peer review so that experts can examine the discrete gadget constructions.

Referee Report

2 major / 2 minor

Summary. The paper claims to prove that deciding whether a given graph G admits a unit-distance realization with all vertices at integer coordinates in Z^2 is NP-complete. The proof proceeds by a polynomial-time reduction from NA3SAT that constructs G via an adaptation of the Eades-Whitesides logic-engine technique, ensuring that G has a Z^2 unit-distance embedding if and only if the input formula is satisfiable.

Significance. If the reduction is correct, the result supplies the first written proof of NP-completeness for this discrete variant of unit-distance realizability, a natural question left open by prior work on the continuous plane. The approach re-uses a standard gadget-based reduction technique rather than inventing new machinery, which is a methodological strength when the adaptation is fully verified.

major comments (2)

[Reduction and gadget construction] The central iff claim of the reduction rests on the correctness of the adapted logic-engine gadgets on Z^2. Because only the four axis-aligned unit vectors exist in the lattice, any gadget that originally relied on non-axis angles or irrational distances must be replaced by new discrete constructions; the manuscript must supply an exhaustive enumeration of all possible local placements for each gadget (including variable, clause, and wire gadgets) and prove that no extraneous configurations satisfy the unit-distance constraints.
[Reduction and gadget construction] The polynomial-time property of the reduction must be verified explicitly for the Z^2 gadgets. The manuscript should state the size of the constructed graph as a function of the NA3SAT instance size and confirm that the new discrete gadgets remain linear (or at worst polynomial) in the number of variables and clauses.

minor comments (2)

[Introduction] The abstract states that the result 'has never been written up'; the introduction should cite the closest related results on unit-distance graphs in the plane and on grid embeddings to clarify the precise novelty.
[Reduction and gadget construction] Notation for the logic-engine components (e.g., how variables and clauses are encoded as subgraphs) should be introduced with a small illustrative example before the general construction.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful review and for emphasizing the need for explicit verification of the gadget correctness and reduction complexity. We address the two major comments point by point below.

read point-by-point responses

Referee: The central iff claim of the reduction rests on the correctness of the adapted logic-engine gadgets on Z^2. Because only the four axis-aligned unit vectors exist in the lattice, any gadget that originally relied on non-axis angles or irrational distances must be replaced by new discrete constructions; the manuscript must supply an exhaustive enumeration of all possible local placements for each gadget (including variable, clause, and wire gadgets) and prove that no extraneous configurations satisfy the unit-distance constraints.

Authors: We agree that the iff direction requires ruling out extraneous placements. The manuscript adapts the Eades-Whitesides logic engine by replacing non-axis gadgets with axis-aligned Z^2 constructions whose unit-distance constraints (limited to the four directions) are argued to enforce the intended variable and clause propagations. To make this fully rigorous, the revised manuscript will add an explicit case analysis enumerating all possible local placements around each gadget type and proving that only the intended configurations satisfy the constraints without allowing unintended solutions. revision: yes
Referee: The polynomial-time property of the reduction must be verified explicitly for the Z^2 gadgets. The manuscript should state the size of the constructed graph as a function of the NA3SAT instance size and confirm that the new discrete gadgets remain linear (or at worst polynomial) in the number of variables and clauses.

Authors: We concur that an explicit complexity statement strengthens the presentation. The revised manuscript will include a dedicated paragraph stating that each gadget (variable, clause, wire) has constant size and that the overall graph has O(v + c) vertices and edges, where v and c are the numbers of variables and clauses in the NA3SAT instance. This establishes that the reduction is linear-time (hence polynomial-time). revision: yes

Circularity Check

0 steps flagged

No circularity: standard reduction from external NP-complete problem via cited gadget technique

full rationale

The paper establishes NP-completeness of unit-distance realizability in Z^2 by a polynomial-time reduction from NA3SAT, constructing a graph via an adaptation of the Eades-Whitesides logic engine. This matches none of the enumerated circularity patterns: there are no self-definitional equations, no fitted parameters renamed as predictions, no load-bearing self-citations, and no ansatz or renaming of known results. The cited logic-engine technique is external (Eades and Whitesides), and the claim rests on the correctness of the discrete gadget adaptation rather than any input-output equivalence by construction. The derivation chain is therefore self-contained against the external benchmark of NA3SAT.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Abstract-only review supplies no explicit free parameters, invented entities, or additional axioms beyond reliance on the known NP-completeness of NA3SAT.

axioms (1)

standard math NA3SAT is NP-complete
The reduction starts from this established result.

pith-pipeline@v0.9.0 · 5593 in / 1142 out tokens · 47807 ms · 2026-05-25T07:36:25.336775+00:00 · methodology