Graph Density, Distance & Planarity

← Back to Domain-Specific Families

Abstractions about cliques, matchings, degree, girth, width, planarity, density, geometric realizability, and constrained graph classes.

11 abstractions in this family — domain-specific abstractions that sit near one another in structural-signature space (k-means over structural-signature embeddings). Each is shown with its short description.

• Cage (Graph Theory) — An r-regular graph of girth g having the minimum possible number of vertices among all graphs with that degree and girth.
• Clique (Graph Theory) — A vertex subset of an undirected graph in which every two distinct vertices are adjacent, equivalently an induced complete subgraph.
• Degree diameter problem — Maximize the number of vertices in a finite graph subject to simultaneous maximum-degree and diameter bounds, comparing constructions with the breadth-first Moore upper bound.
• Dense Graph — A graph whose edge population is a substantial, usually non-vanishing fraction of all possible vertex pairs, placing it in the quadratic-edge rather than sparse regime under a declared asymptotic convention.
• Girth (Graph Theory) — Assign an undirected graph the length of its shortest cycle, using infinity for an acyclic graph, to quantify how far local neighborhoods remain tree-like.
• 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.
• Ice-Type Model — Model a four-coordinated lattice with arrow variables constrained to two-in/two-out at every vertex, then weight the six allowed local configurations to derive global statistical behavior.
• Matching — Cast a pairing problem as a largest (or minimum-cost, or perfect) set of pairwise vertex-disjoint edges on an explicit graph, then split on bipartiteness to select the theorems and polynomial-time algorithm that solve it.
• Nut Graph — A finite simple graph whose adjacency matrix has a one-dimensional kernel generated by a vector nonzero at every vertex, making zero a simple eigenvalue with full vertex support.
• Pathwidth — Measure how narrowly a graph can be arranged along a path by minimizing the largest bag size minus one over path decompositions with vertex continuity and edge coverage.
• Planarity — The graph property of admitting a crossing-free drawing in the plane — pinned by Kuratowski/Wagner to a finite obstruction (no K₅ or K₃,₃) and by Euler's formula to a density bound, which is why a shelf of NP-hard problems turns polynomial on planar graphs.