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: v3 · 2026-09-19 · History
Domain-specific #: 1956
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomain: Geometric Graph Theory → Mathematics
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.

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.

How would you explain it like I'm…

Same-Size Bubble Puzzle

Say you have a picture of friends, with lines between kids who are friends. Give each kid a ball, all the same size. Can you put the balls along a line, or on a table, or up in a room, so two balls touch exactly when those kids are friends? The fewest directions you need is the sphericity.

Fewest Dimensions for Equal Balls

Take a graph of dots and lines. Try to give each dot a ball, all exactly the same size, placed somewhere in space. The rule: two balls overlap exactly when their dots are joined by a line, never otherwise. Some graphs can be done with balls on a line (1 dimension), some need a flat plane (2), some need 3-D space or even more dimensions. The sphericity is the smallest number of dimensions that works perfectly.

Unit-Ball Representation Dimension

Sphericity measures how many dimensions a graph needs to be drawn as overlapping equal-size balls. Give every vertex a point in d-dimensional space and pick one distance threshold for all pairs. The drawing must be exact: two vertices are adjacent if and only if their points are within the threshold, which is the same as their equal balls intersecting. The sphericity is the smallest d where such an exact representation exists. Whether 'touching' counts as intersecting depends on an open or closed ball convention, which you have to fix.

The sphericity of a graph is the least Euclidean dimension d in which it is the intersection graph of congruent spheres, equivalently unit balls under a fixed convention. Concretely, assign each vertex a point in R^d and fix a single distance threshold; vertices must be adjacent exactly when their points lie within that threshold. This is equivalent to congruent balls intersecting, with the open/closed convention determining boundary cases. Both directions matter: non-adjacent vertices must be farther apart than the threshold, so it is not enough to place neighbors close. The invariant is the minimum d admitting such an exact representation. It is a specific geometric representation parameter, not the general topic of geometric graphs.

Scope of Application¶

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

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.

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.

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.

Relationships to Other Abstractions¶

Current abstraction Graph Sphericity Domain-specific

Parents (1) — outgoing typed relations

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 → is a kind of Dimension

Neighborhood in Abstraction Space¶

Graph Sphericity sits in a moderately populated region (44^th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.

Family — Graph Structures & Combinatorial Objects (46 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25