Graph Sphericity¶

The least Euclidean dimension in which a graph can be represented as the intersection graph of congruent spheres, equivalently unit balls under the adopted convention.

Version: v2 · 2026-09-06 · History
Domain-specific #: 1956
Origin domain: mathematics
Subdomain: geometric graph theory
Aliases: Sphericity of a graph

Core Idea¶

Graph Sphericity is the least Euclidean dimension in which a graph can be represented as the intersection graph of congruent spheres, equivalently unit balls under the adopted convention. ^[1]

Assign every graph vertex a point in R^d and fix one distance threshold, or equivalently assign congruent balls. Two vertices are adjacent exactly when their points lie within the threshold, equivalently when the corresponding balls intersect under the chosen open/closed convention. The sphericity is the smallest d for which an exact representation exists.

The operative boundary is exact: The minimum-dimensional congruent-sphere intersection representation remains uncovered. The abstraction is therefore not the topic named by its field, but the reusable role structure specified below.

Structural Signature¶

Sig role-phrases:

the finite graph G — the adjacency pattern to be represented
the Euclidean ambient space R^d — the candidate geometric dimension
the vertex centers — one point assigned to each graph vertex
the common distance threshold — the scale shared by every pairwise adjacency test
the exact adjacency equivalence — edge if and only if distance is below the threshold
the congruent-ball representation — the equivalent intersection-graph view
the dimension minimization — the least d admitting any valid representation
the realization convention — strict versus non-strict threshold and coincident-center allowances

Recognition test. A case qualifies only when its roles can be mapped to the declared the finite graph G, the Euclidean ambient space R^d, the vertex centers, the common distance threshold, and when the characteristic boundary conditions are preserved. Surface vocabulary or a loose analogy is insufficient.

What It Is Not¶

Not planarity. Planarity asks for a crossing-free drawing in two dimensions, not a congruent-ball intersection representation.
Not sphere packing dimension. Nonadjacent balls need not form a packing when the graph contains edges.
Not arbitrary-radius ball graphs. All balls must be congruent.
Not one chosen embedding's dimension. Sphericity minimizes over every exact representation.
Not a topological invariant. Euclidean distances and a uniform threshold are essential.
Not graph diameter. Diameter measures path length inside G, not ambient representation dimension.

Scope of Application¶

The abstraction has a bounded but recurring habitat. These are literal applications of the same domain machinery, not cross-domain metaphors. ^[1]

Geometric graph representation. abstract adjacency is realized by uniform-distance proximity.
Dimension bounds. graph classes are compared by upper and lower bounds on required Euclidean dimension.
Intersection graph theory. congruent balls supply a tightly constrained intersection model.
Proximity networks. the invariant asks whether a network can arise from one distance threshold in low dimension.
Extremal graph theory. families with unusually high or low sphericity reveal limits of geometric encoding.

Clarity¶

Scale is irrelevant: any positive threshold can be rescaled to a fixed value. What matters is a single threshold for every pair and the biconditional, not merely that edges join close points. A drawing where some nonedges also lie below the threshold is not a realization.

A useful audit proceeds in order: identify the candidate roles, verify their types and quantifiers, apply the recognition test, and then test every stated exclusion. If a case supplies only the broad parent pattern while dropping the domain accent, it is not Graph Sphericity.

Manages Complexity¶

Sphericity turns an open-ended geometric representation question into one integer invariant. It separates graph structure compatible with low-dimensional uniform proximity from structure requiring additional coordinates, allowing bounds to replace exhaustive search over point configurations.

The compression remains accountable because every simplification has a named validity condition. A user can ask which role is missing, which assumption fails, and which neighboring abstraction should replace the candidate instead of treating the label as an unanalyzed bundle.

Abstract Reasoning¶

R1. Fix the strict or non-strict intersection convention.

R2. Normalize the common threshold by rescaling.

R3. Verify both directions of the edge-distance biconditional.

R4. Distinguish an upper-bound construction from a proof of minimality.

R5. Use graph-class theorems only under their exact finiteness and simplicity assumptions.

The reasoning pattern is deliberately typed: definitions establish identity, calculations or constructions establish consequences, and empirical or institutional evidence establishes whether a real case instantiates the roles. One kind of support cannot silently substitute for another.

Knowledge Transfer¶

The invariant transfers literally to any finite simple graph represented by congruent Euclidean balls. Generic dimension and representation ideas travel farther, but 'sphericity' should not be used for arbitrary latent embeddings, unequal radii, or similarity scores without the exact threshold semantics.

The transfer boundary follows from the classification test: The invariant recurs across geometric graph theory and embedding problems, but adjacency-as-intersection, congruent sphere or ball convention, ambient Euclidean dimension, and minimization are constitutive. The safe portable move is to name the broader parent when the home-domain machinery is absent and to retain the domain name only when literal recognition succeeds.

Examples¶

Canonical: a complete graph¶

Every vertex of K_n can be assigned centers within one threshold of each other in one-dimensional Euclidean space, so every pair is adjacent. Under conventions permitting a zero-dimensional coincident realization, the base case may shift; this is why the ambient and coincidence convention must be stated before reporting the numerical invariant. ^[1]

Mapped back: the finite graph G; the vertex centers; the common distance threshold; the exact adjacency equivalence; the realization convention.

Applied / In Practice: proving an upper bound¶

To show a graph class has sphericity at most d, construct one point per vertex in R^d and choose a common threshold. Then verify every edge is short and every nonedge is long. This supplies an upper bound only. A matching lower bound needs an obstruction showing no configuration in R^(d-1) can satisfy all pairwise inequalities. ^[1]

Mapped back: the Euclidean ambient space; the exact adjacency equivalence; the dimension minimization; the congruent-ball representation.

Structural Tensions¶

T1: Exact representation versus approximate embedding. Real data embeddings tolerate error, while sphericity changes identity if any adjacency is misclassified. Diagnostic: Is the task exact graph realization or low-distortion approximation?

T2: Uniform radius versus expressive power. Congruent balls make the invariant sharp but can require more dimensions than variable-radius models. Diagnostic: Are all proximity objects truly the same size?

T3: Construction versus minimality. A coordinate assignment proves an upper bound, not the least possible dimension. Diagnostic: What rules out one fewer dimension?

T4: Strict threshold versus boundary contacts. Open and closed ball conventions can disagree when distances equal the threshold. Diagnostic: How are equality cases treated?

T5: Graph abstraction versus geometric interpretation. Many nongeometric networks admit formal representations that have no causal spatial meaning. Diagnostic: Is geometry explanatory or only representational?

T6: Domain autonomy vs prime reduction. Dimension and representation are portable, but the minimum congruent-ball intersection dimension is a specific graph invariant. Diagnostic: Does a generic dimension parent entail the adjacency biconditional and equal radii? If not, retain the domain node.

Structural–Framed Character¶

The five-criterion aggregate is 0.05 (structural). The classification is reasoned rather than cosmetic:

Vocabulary travels — structural (0.25). The operative vocabulary retains the home-domain types named in the Structural Signature even when a thinner parent pattern travels.
Evaluative weight — structural (0.00). The score records whether applying the abstraction requires a normative or interpretive judgment in addition to structural recognition.
Institutional origin — structural (0.00). The score records whether the abstraction is constituted by a scholarly, legal, technical, or administrative convention rather than merely discovered in nature.
Human-practice bound — structural (0.00). The score records how far the named roles depend on a human practice, measurement regime, language, or institution.
Import versus recognize — structural (0.00). Beyond its home habitat, use of the name increasingly becomes import by analogy rather than recognition of the same mechanism.

The portable skeleton is: find the smallest representational resource in which a relation can be realized by one uniform local test. That skeleton belongs to the related parent abstractions; it does not make the fully accented node a prime. Its character: structural, with a real structural core whose recognition remains bounded by domain-specific types and validity conditions.

Structural Core vs. Domain Accent¶

This section decides why Graph Sphericity is a domain-specific abstraction rather than a prime.

Structural core: Find the smallest representational resource in which a relation can be realized by one uniform local test. This relational skeleton can recur outside the home domain and is the part legitimately carried by broader primes.

Domain accent: Finite graphs, euclidean distance, congruent balls, exact adjacency, and minimum ambient dimension. Remove those types and constraints and the result may still resemble the skeleton, but it is no longer recognized as this named abstraction.

Why it does not clear the prime bar: The skeleton belongs to dimension and representation; graph sphericity is the exact uniform-proximity invariant defined by its geometric graph semantics. Cross-domain transfer is therefore routed through the parents, while the named entry remains available for precise in-domain diagnosis.

Planarity. is a neighboring minimum-dimensional drawing property with different constraints.
Tree (Graph Theory). is a graph class whose sphericity can be studied.
Dimension. supplies the minimized resource but not the realization rule.

These are prose relations only. They do not create structured DAG edges, and placement must still pass the live endpoint, redundancy, and cycle checks recorded in the bundle's placement memo.

Relationships to Other Abstractions¶

Current abstraction Graph Sphericity Domain-specific

Parents (1) — more general patterns this builds on

Graph Sphericity is a kind of Dimension Prime

Planarity. is a neighboring minimum-dimensional drawing property with different constraints.

Hierarchy path (1) — routes to 1 parentless root

Graph Sphericity → Dimension

Neighborhood in Abstraction Space¶

Graph Sphericity sits in a sparse region of the domain-specific corpus (61^st percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Graph Density, Distance & Planarity (11 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With¶

Planarity. crossing-free embedding in the plane. Tell: Are edges drawn as curves or induced by distance?
Boxicity. minimum dimension for intersection graphs of axis-aligned boxes. Tell: Are the representing objects boxes or congruent balls?
Unit disk graph recognition. the fixed two-dimensional membership question. Tell: Is d fixed at two or minimized?
Euclidean graph dimension. other notions preserve edge lengths or all distances. Tell: What pairwise relation must the embedding preserve?
Graph diameter. maximum shortest-path distance. Tell: Is distance intrinsic to the graph or ambient Euclidean space?

References¶

[1] Hiroshi Maehara, “Space Graphs and Sphericity”, Discrete Applied Mathematics 7(1) (1984), 55–64. registry ↩a ↩b ↩c ↩d