Contact graph¶

Represent a family of geometric objects by one vertex per object and an edge exactly when two objects satisfy a declared boundary-contact relation without prohibited interior overlap or crossing, making the permitted notion of touching part of the graph class.

Version: v2 · 2026-08-30 · History
Domain-specific #: 1548
Origin domain: mathematics
Subdomain: geometric graph theory

Core Idea¶

A contact graph has one vertex for each object in a geometric family and an edge between two vertices when the corresponding objects touch according to a specified contact rule, ordinarily without crossing or overlapping interiors.^[1]^[1] geometry induces adjacency: the object representation fixes which pairs meet at allowed boundary points or segments, and forgetting coordinates while retaining those adjacencies yields an abstract graph whose realizability depends on object shape and contact constraints.

Its autonomous residual is the graph induced by a restrictive geometric touching relation and the existence of a compatible object representation, rather than unrestricted set intersection, proximity, graph drawing, or a graph product. The identity fails when interior overlap counts despite being forbidden, near contact is accepted by tolerance without convention, edge crossings in a drawing are confused with object contact, multiple-contact degeneracies change adjacency unnoticed, one object represents several vertices, or a contact representation is claimed without checking nonedges.

Recognition requires an analyst to state the object class and ambient space, define contact precisely, verify every edge and nonedge against the geometry, test forbidden crossings or overlaps, record whether multiple objects may share one contact point, and separate existence of a representation from one drawing. Once established, it supports studying circle packings, planar graph representations, penny graphs, rectangle and segment contacts, recognition and realization problems, geometric constraints on adjacency, and layout constructions without turning those uses into the definition.

Structural Signature¶

Carrier: a finite or explicitly bounded family of geometric objects embedded in an ambient space, together with a typed notion of admissible contact
Inputs or antecedent state: object family, ambient dimension and geometry, interiors and boundaries, permitted tangency or shared-boundary relation, overlap and crossing exclusions, degeneracy policy, and the abstract vertex correspondence
Constitutive operation: geometry induces adjacency: the object representation fixes which pairs meet at allowed boundary points or segments, and forgetting coordinates while retaining those adjacencies yields an abstract graph whose realizability depends on object shape and contact constraints
Invariant: there is a declared object-to-vertex bijection and edge equivalence with admissible geometric contact, with interior overlap, crossing, containment, higher-order meetings, and degeneracies handled by explicit convention
Recognition test: state the object class and ambient space, define contact precisely, verify every edge and nonedge against the geometry, test forbidden crossings or overlaps, record whether multiple objects may share one contact point, and separate existence of a representation from one drawing
Output or consequence: studying circle packings, planar graph representations, penny graphs, rectangle and segment contacts, recognition and realization problems, geometric constraints on adjacency, and layout constructions
Failure boundary: interior overlap counts despite being forbidden, near contact is accepted by tolerance without convention, edge crossings in a drawing are confused with object contact, multiple-contact degeneracies change adjacency unnoticed, one object represents several vertices, or a contact representation is claimed without checking nonedges

What It Is Not¶

It is not the whole field of mathematics; many objects in that field do not satisfy its constitutive rule.
It is not its canonical example. The circle-packing theorem represents every finite planar graph by disks with disjoint interiors whose tangencies encode its edges. That is an instance, not a definition.
It is not Network. Network is the strict parent representing pairwise interactions; a contact graph requires a geometric realization whose exact admissible touching relation generates the edges.
It is not an unrestricted metaphor. if three or more objects meet at one point, pairwise adjacency may create a clique even though contacts are not separated; some representation theorems forbid or perturb such degeneracy and others allow it

Scope of Application¶

Contact graph applies when the analyst can specify a finite or explicitly bounded family of geometric objects embedded in an ambient space, together with a typed notion of admissible contact and establish that there is a declared object-to-vertex bijection and edge equivalence with admissible geometric contact, with interior overlap, crossing, containment, higher-order meetings, and degeneracies handled by explicit convention. The entry treats graph representations and realizability; physical contact mechanics, force transmission, friction, and tolerance engineering require additional models not contained in adjacency alone.^[2]

Recognition. state the object class and ambient space, define contact precisely, verify every edge and nonedge against the geometry, test forbidden crossings or overlaps, record whether multiple objects may share one contact point, and separate existence of a representation from one drawing
Comparison. Compare legitimate instances through object class, ambient dimension, congruence, convexity, interior disjointness, contact dimension, corner versus side contact, multiple contacts, planarity, recognition complexity, and representation uniqueness.
Boundary. if three or more objects meet at one point, pairwise adjacency may create a clique even though contacts are not separated; some representation theorems forbid or perturb such degeneracy and others allow it
Use. Preserve every assumption when using the identity for studying circle packings, planar graph representations, penny graphs, rectangle and segment contacts, recognition and realization problems, geometric constraints on adjacency, and layout constructions.

Clarity¶

A clear claim names the carrier, governing rule, assumptions, and recognition test. This matters because touching can mean point tangency, shared positive-length boundary, closed-set intersection, or tolerance-based proximity, and different conventions define different graph classes. The disciplined statement is that the object counts as Contact graph exactly when there is a declared object-to-vertex bijection and edge equivalence with admissible geometric contact, with interior overlap, crossing, containment, higher-order meetings, and degeneracies handled by explicit convention

Identity and measurement remain separate. Computational geometry must manage finite precision, near tangency, overlapping boundaries, and degeneracy; exact certificates or declared tolerance policies are needed when coordinates are approximate. Approximation or noisy evidence may weaken a classification without changing its definition.

Manages Complexity¶

The abstraction compresses circle and disk contacts, penny graphs, smooth convex-body packings, rectangle and square contacts, polygon, segment, arc, triangle, three-dimensional body contacts, weighted contacts, and degenerate or generic-position conventions into a stable carrier, rule, invariant, and failure boundary. It makes comparison tractable while retaining the variables that control validity.

Compression can hide assumptions. A responsible use therefore declares object class, ambient dimension, congruence, convexity, interior disjointness, contact dimension, corner versus side contact, multiple contacts, planarity, recognition complexity, and representation uniqueness and returns to the full diagnostic whenever a convention or boundary case changes.

Abstract Reasoning¶

Type the carrier. Establish a finite or explicitly bounded family of geometric objects embedded in an ambient space, together with a typed notion of admissible contact and reject examples from a different problem.
Lock the rule. Express that there is a declared object-to-vertex bijection and edge equivalence with admissible geometric contact, with interior overlap, crossing, containment, higher-order meetings, and degeneracies handled by explicit convention independently of one notation or implementation.
Derive carefully. Infer studying circle packings, planar graph representations, penny graphs, rectangle and segment contacts, recognition and realization problems, geometric constraints on adjacency, and layout constructions only under the stated assumptions.
Stress-test. Contrast the legitimate boundary case—if three or more objects meet at one point, pairwise adjacency may create a clique even though contacts are not separated; some representation theorems forbid or perturb such degeneracy and others allow it—with this counterexample: an intersection graph of overlapping disks is not a disk contact graph when interiors overlap, even if the abstract graph is identical to one that has a separate contact representation.

Knowledge Transfer¶

Transfer within mathematics is strong when new cases preserve the same carrier, mechanism, and diagnostic. The move from The circle-packing theorem represents every finite planar graph by disks with disjoint interiors whose tangencies encode its edges. to A floorplanning abstraction represents interior-disjoint rectangles as vertices and shared boundary segments as adjacencies. demonstrates that continuity.^[3]

Outside the domain, only the skeleton—replace spatial objects by nodes and retain exactly the adjacency created at their permitted boundaries while discarding most geometric detail—travels automatically. The terms contact graph, tangency graph, object representation, boundary, interior, packing, circle packing, coin graph, penny graph, planar graph, realization, and degeneracy retain domain-specific meanings, so every role and inference must be revalidated.

Examples¶

Canonical¶

The circle-packing theorem represents every finite planar graph by disks with disjoint interiors whose tangencies encode its edges. Vertices map to disks and abstract adjacency maps to tangency; disjoint interiors enforce the contact boundary and make the representation more restrictive than arbitrary circle intersection.^[2] It is canonical because the carrier, rule, invariant, and consequence are all inspectable.^[1]

Mapped back: a finite or explicitly bounded family of geometric objects embedded in an ambient space, together with a typed notion of admissible contact → geometry induces adjacency: the object representation fixes which pairs meet at allowed boundary points or segments, and forgetting coordinates while retaining those adjacencies yields an abstract graph whose realizability depends on object shape and contact constraints → there is a declared object-to-vertex bijection and edge equivalence with admissible geometric contact, with interior overlap, crossing, containment, higher-order meetings, and degeneracies handled by explicit convention → studying circle packings, planar graph representations, penny graphs, rectangle and segment contacts, recognition and realization problems, geometric constraints on adjacency, and layout constructions

Applied / In Practice¶

A floorplanning abstraction represents interior-disjoint rectangles as vertices and shared boundary segments as adjacencies. The graph captures which regions touch but not contact length, orientation, area, or routing capacity unless those are added as attributes, and corner-only contact must be declared.^[3] It qualifies only after the same diagnostic and failure boundary are checked.^[2]

Mapped back: declared instance → recognition test → boundary check → qualified use

Structural Tensions¶

T1: Exact identity vs. practical recognition. The constitutive condition may be exact while evidence is indirect. Diagnostic: Can the reviewer state both the condition and the warrant?
T2: Canonical form vs. variants. circle and disk contacts, penny graphs, smooth convex-body packings, rectangle and square contacts, polygon, segment, arc, triangle, three-dimensional body contacts, weighted contacts, and degenerate or generic-position conventions can preserve or change the identity. Diagnostic: Which named role is invariant across the variants?
T3: Compression vs. hidden assumptions. The label is useful only while prerequisites remain visible. Diagnostic: Can each downstream inference be traced to a declared assumption?
T4: Autonomy vs. reduction. The candidate uses broader structures but claims the graph induced by a restrictive geometric touching relation and the existence of a compatible object representation, rather than unrestricted set intersection, proximity, graph drawing, or a graph product. Diagnostic: Does that residual still support independent recognition after the parent and neighbors are subtracted?

Structural–Framed Character¶

The entry is structurally mixed but domain-framed. Its portable skeleton is replace spatial objects by nodes and retain exactly the adjacency created at their permitted boundaries while discarding most geometric detail; its identity-bearing terms are contact graph, tangency graph, object representation, boundary, interior, packing, circle packing, coin graph, penny graph, planar graph, realization, and degeneracy. Those terms determine admissible objects, evidence, and consequences inside mathematics.

Structural Core vs. Domain Accent¶

The structural core is a carrier governed by geometry induces adjacency: the object representation fixes which pairs meet at allowed boundary points or segments, and forgetting coordinates while retaining those adjacencies yields an abstract graph whose realizability depends on object shape and contact constraints and tested by state the object class and ambient space, define contact precisely, verify every edge and nonedge against the geometry, test forbidden crossings or overlaps, record whether multiple objects may share one contact point, and separate existence of a representation from one drawing. The domain accent is constitutive rather than decorative, so an analogy that preserves only the skeleton is not another instance of Contact graph.

The proposed strict upward parent is prime:network. The resulting graph is literally a network of vertices linked by a pairwise relation; geometric objects, boundary tangency, nonoverlap, realizability, and degeneracy rules supply the autonomous mathematical residual. The edge is proposal-only and points to a frozen prior-baseline Prime.

The entry does not collapse into the parent because the graph induced by a restrictive geometric touching relation and the existence of a compatible object representation, rather than unrestricted set intersection, proximity, graph drawing, or a graph product A thematic neighbor is declined whenever it does not literally subsume that rule.

The prospective workspace queue contains one strict upward edge to prime:network. No live DAG mutation is authorized.

Relationships to Other Abstractions¶

Current abstraction Contact graph Domain-specific

Parents (1) — more general patterns this builds on

Contact graph is a kind of Network Prime

The proposed strict upward parent is prime:network.

Hierarchy path (1) — routes to 1 parentless root

Contact graph → Network → Reservoir-Flux Network → Conservation Laws → Invariance

Neighborhood in Abstraction Space¶

Contact graph sits in a crowded region of the domain-specific corpus (37^th percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.

Family — Convex Geometry & Spatial Partition (35 abstractions)

Nearest neighbors

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

Not to Be Confused With¶

Intersection graph. Joins objects whenever their sets intersect, usually allowing interior overlap; contact graphs impose a stricter meeting relation.
Coin graph. A contact graph of circles or disks, often with particular interior-disjoint conventions.
Penny graph. The unit-circle contact subclass.
Planar graph drawing. Represents vertices as points and edges as curves; it is not necessarily an object-contact representation.
Proximity graph. Creates edges from distance or neighborhood rules rather than exact boundary contact.

References¶

[1] Paul Koebe, 'Kontaktprobleme der konformen Abbildung,' Berichte über die Verhandlungen der Sächsischen Akademie der Wissenschaften zu Leipzig, Mathematisch-Physische Klasse 88, 141–164 (1936). registry ↩a ↩b ↩c

[2] Oded Schramm, 'Square Tilings with Prescribed Combinatorics,' Israel Journal of Mathematics 84, 97–118 (1993), DOI 10.1007/BF02761693. registry ↩a ↩b ↩c

[3] Giuseppe Di Battista, Peter Eades, Roberto Tamassia, and Ioannis G. Tollis, Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, 1999, chapters on planar and visibility representations, ISBN 978-0-13-301615-4. registry ↩a ↩b