Graph Structures & Combinatorial Objects

← Back to Domain-Specific Families

Abstractions that formalize discrete, graph-based and cellular structures — graph invariants and colorings (arboricity, edge and fractional coloring), decompositions and embeddings (biconnected components, planarity, duality), algebraically defined graphs (Cayley, hypercube, zero-divisor graphs), polytopes and polyhedral complexes, and applied abstractions like topological sorting.

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

• Arboricity — Measure a graph's edge density by the fewest acyclic forest layers needed to partition all its edges.
• Arrangement of Pseudolines — A finite family of line-like curves crosses pairwise exactly once, preserving line-arrangement combinatorics without requiring straight-line realization.
• Aztec Diamond — Use an order-indexed diamond-shaped square-lattice region whose domino exact covers support a power-of-two enumeration, reversible shuffling, path representations, and an arctic-circle limit shape.
• Biconnected Component — A maximal connected edge-bearing block of an undirected graph with no internal articulation vertex, counting a bridge as a one-edge block under an explicit convention.
• Branch Decomposition — A tree arrangement of a graph's edges whose cuts expose shared-vertex interfaces, allowing the arrangement's largest interface to be measured.
• Cayley Graph — A graph with group elements as vertices and edges given uniformly by multiplication by a chosen generating set.
• Comparability Graph — Join exactly the comparable pairs of a partial order in an undirected graph, equivalently requiring that its edges admit a transitive orientation.
• Connected Dominating Set — A vertex subset of an undirected graph that dominates every excluded vertex while inducing a connected subgraph on its selected vertices.
• Dependency Hell — The pathological state where a project's transitive dependency closure holds mutually incompatible version constraints, turning installation into an NP-complete constraint-satisfaction problem that no edge-level patch can resolve.
• Desargues's Theorem — A projective-incidence rule linking concurrence of corresponding triangle-vertex lines to collinearity of corresponding side intersections in a Desarguesian setting.
• Edge Coloring — Assign colors to graph edges so that no two edges sharing a vertex receive the same color.
• Eigenvector Centrality — A network node score recursively weighted by the scores of connected nodes and selected from a leading adjacency eigenvector.
• Epigraph — The upward-closed set of real-height pairs above an extended-real-valued function, preserving each function value as a fiber infimum.
• Finite subdivision rule — A finite recursive prescription replacing each tile type by a patterned subdivision to generate successively finer cell structures.
• Fractional Coloring — Conflict-free assignment of multiple colors per graph vertex, optimized by palette size per assigned color.
• Generalized blockmodeling of binary networks — Generalized blockmodeling of binary networks partitions actors into positions and compares observed relation blocks with ideal binary block types by minimizing explicitly defined inconsistency errors.
• Graph canonization — The problem of computing a canonical labeled representative shared by every graph in an isomorphism class.
• Graph Data Type — The programmatic abstraction representing entities as nodes and relationships as edges behind a traversal/mutation/query interface — insulating algorithm code from the in-memory layout so representation becomes a profiling-driven swap, not a rewrite.
• Graph Duality — Pair a planar graph with a dual by placing a vertex inside each face and joining faces that share an edge, so vertices swap with faces and problems translate across a lossless table — paths become cuts, colorings become face colorings — letting you solve whichever side is easier.
• Graph Embedding — A crossing-free placement of a graph's vertices and edge arcs on a specified topological surface that preserves their incidences.
• 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.
• Hadwiger number — The largest integer k such that the complete graph on k vertices occurs as a minor of a given undirected graph.
• Hook Length Formula — Count standard Young tableaux of a partition shape by dividing n! by the product of its cell hook lengths.
• Hyperbolic Geometric Graph — A graph model that positions vertices in hyperbolic space and makes edges depend on the vertices' hyperbolic distance.
• Hyperbolization Procedures — Hyperbolization procedures replace and glue cells of a complex to build a controlled nonpositively or negatively curved space.
• Hypercube Graph — The graph on all n-bit strings with an edge exactly when two strings differ in one bit.
• Induced Path — A graph path whose selected vertices have no host-graph edges except the consecutive edges of the path.
• Kramers–Wannier Duality — A lattice-model strong–weak coupling correspondence that matches one model's high-temperature graphs to a dual model's low-temperature defects, relating normalized partition functions subject to boundary-sector conditions.
• Linked Open Data Release — Publish a dataset as a machine-traversable RDF graph with HTTP-dereferenceable identifiers, an explicit open license, and outbound links to other graphs — so downstream systems can resolve, link into, and traverse it without bilateral negotiation.
• List coloring — List coloring denotes generalization of graph coloring in which each vertex has a list of allowed colors in graph coloring.
• 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.
• Metric dimension (graph theory) — The minimum size of a vertex subset whose distance vectors uniquely identify every graph vertex.
• Mixed Chinese Postman Problem — Find a least-cost closed walk covering every link of a weighted graph with undirected edges and directed arcs.
• Modular product of graphs — A graph product on the Cartesian product of two vertex sets whose adjacency encodes agreement of adjacency or nonadjacency in the factor graphs.
• Newest Vertex Bisection — A labeled triangle-mesh refinement rule that inherits midpoint vertices and completes neighbor splits to retain a conforming, shape-regular mesh.
• Nine-Point Conic — The conic through the six side midpoints and three diagonal points determined by a complete quadrangle, with circle and hyperbola cases governed by the quadrangle geometry.
• 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 that makes planar graphs sparse; planar structure also makes some NP-hard problems, such as max-cut, polynomial, though others, such as Hamiltonian cycle, stay NP-hard.
• Polyhedral Complex — A face-closed collection of convex polyhedra whose pairwise intersections are common faces, assembling coherent geometric cells.
• Polytope — A finite-dimensional flat-sided geometric or ranked-incidence object that generalizes polygons and polyhedra under an explicit convexity, boundedness, realization, and face convention.
• Topological Sorting — Produce a linear order over the nodes of a directed acyclic graph so every edge runs forward — every dependency before its dependent — by repeatedly emitting any node with no unmet prerequisite, well-defined exactly when the graph has no cycle.
• Two-Terminal Series–Parallel Graph — A source–sink edge network built recursively from single edges by terminal-preserving series and parallel joins.
• Uniform space — A set equipped with a uniform structure that formalizes relative closeness and supports uniform continuity, convergence, and completeness without a chosen metric.
• Vertex Cover in Hypergraphs — A vertex subset that intersects every hyperedge, with feasibility distinct from inclusion-minimality or minimum size.
• Zero-Divisor Graph — A zero-divisor graph connects distinct nonzero zero divisors of a commutative ring when their product is zero, exposing annihilation structure while forgetting other ring data.