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

v3 · 2026-09-19 · History

Domain-specific #

1548

Domain group

Formal Sciences

Origin domain

Mathematics

Subdomain

Geometric Graph Theory → Mathematics

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. 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.

How would you explain it like I'm…

Touching Coins Picture

Put some coins on a table so that some are touching and none are on top of each other. Now draw a dot for each coin, and draw a line between two dots whenever those two coins touch. That dot-and-line picture is a contact graph.

Who Touches Whom

A contact graph is made from a bunch of shapes, like circles or rectangles, that can touch but not overlap. Each shape becomes a dot, and two dots get connected by a line only if their shapes touch. Just being close isn't enough; they have to really touch by the rule you picked. You also have to check the other way: shapes that aren't connected in the graph must not be touching.

Graphs From Touching Shapes

A contact graph has one vertex per object in a family of geometric objects, and an edge between two vertices exactly when the objects touch according to a stated contact rule, usually with interiors not overlapping. It's different from an intersection graph, where overlapping counts, or a graph built from objects just being close. The geometry decides which pairs touch; forgetting the positions but keeping the touching pattern gives an abstract graph. A key question is whether a given graph can be represented this way with a certain kind of shape. To check a representation, you must confirm both that every edge corresponds to a real contact and that every non-edge corresponds to shapes that don't touch.

 

A contact graph is the graph induced by a geometric touching relation: each object in a family becomes a vertex, and two vertices are adjacent when their objects touch according to a specified contact rule, ordinarily with interiors disjoint. Geometry determines adjacency, and forgetting coordinates while keeping the adjacencies gives an abstract graph; whether a given graph can be realized this way depends on the object shapes and the contact constraints. The concept differs from intersection graphs (where overlap is allowed), proximity graphs, graph drawings and graph products. A contact representation must be verified on both edges and non-edges, with interior overlaps and edge crossings excluded, near-contacts not admitted without a stated tolerance, and degeneracies such as multiple objects meeting at one point handled explicitly. The existence of a representation must also be separated from any particular drawing. Contact graphs underlie the study of circle packings, planar graph representations, penny graphs, rectangle and segment contacts, and recognition and realization problems.

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.

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

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.

Abstract Reasoning

1. 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.
2. 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.

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.

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.

Relationships to Other Abstractions

Current abstraction Contact graph Domain-specific

Parents (1) — outgoing typed relations

• Contact graph is a kind of Network Prime

  The resulting graph is literally a network of vertices linked by a pairwise relation; What makes it its own entry: 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.

Hierarchy path (1) — routes to 1 parentless root

• Contact graph → is a kind of Network

Neighborhood in Abstraction Space

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

Family — Spatial Data Structures & Meshing (17 abstractions)

Nearest neighbors

• Map graph — 0.91
• Polygon partition — 0.90
• Ambient space (mathematics) — 0.90
• Triangulation (topology) — 0.89
• Ran space — 0.89

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