Graph Structures & Algorithms

← Back to Domain-Specific Families

Abstractions about graphs and their structural or algorithmic properties, including special graph families such as complete bipartite, chordal bipartite and prism graphs, graph-theoretic invariants and operations like edge covering number and graph power, and algorithms or models built on graphs such as Prim's algorithm and graph dynamical systems.

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

• Asymptote — A straight line approached arbitrarily closely by an unbounded branch of a plane curve in a specified limiting direction.
• Blockmodel — A reduced network representation that groups nodes into positions and summarizes ties within and between those groups as blocks.
• Chordal bipartite graph — A bipartite graph in which every cycle of length at least six has a chord, equivalently a bipartite graph with no induced cycle longer than four.
• Complete Bipartite Graph — A bipartite graph K_{m,n} with no within-part edges and every possible edge between its two vertex parts present.
• Cycle Graph (Algebra) — An undirected diagram representing finite-group elements as vertices and cyclic subgroups as identity-sharing polygons.
• Digon — A two-sided polygonal object with two vertices and two edges, degenerate under ordinary straight-sided Euclidean realization but nondegenerate in settings such as spherical geometry.
• Double-Pushout Graph Rewriting — A graph-rewrite semantics that preserves an interface while two pushouts delete and add matched structure.
• Edge Covering Number — The minimum cardinality of an edge cover of a graph: the smallest set of edges incident to every vertex, defined only when isolated vertices are absent or under an explicit extension, and equal to |V| minus the maximum-matching size for finite graphs without isolated vertices.
• Force-Directed Graph Drawing — Placing graph vertices by iteratively relaxing an artificial force or energy model derived from graph relationships.
• Geodetic Graph — An undirected unweighted graph in which every vertex pair has exactly one shortest path, though longer alternate paths and some cycles may exist.
• Graph dynamical system — A discrete dynamical system built from a graph, local vertex states and neighborhood functions, and an update scheme that induces a global state-transition map.
• Graph Invariant — A graph invariant is a value, polynomial, sequence, multiset, or other mathematical object assigned to a graph such that isomorphic graphs receive the same result, with its definition, graph category, and distinguishing power explicitly stated.
• Graph Power — The same-vertex graph transformation that makes every pair at original shortest-path distance at most k directly adjacent.
• Graphical Models for Protein Structure — Probabilistic graphical representations of protein conformations, using structural variables and graph-specified dependencies to reason about geometry.
• Lindström–Gessel–Viennot Lemma — A determinant identity equating path-matrix minors in a weighted directed acyclic graph with a signed sum of vertex-disjoint path families between chosen sources and destinations.
• Loop (Graph Theory) — A graph edge whose two endpoints are the same vertex, admitted or excluded according to the chosen graph category.
• Mass Point Geometry — A triangle-geometry method that represents segment ratios and cevian intersections by assigning balancing masses to points.
• Polygon — A planar geometric figure whose boundary is a finite cyclic sequence of straight line segments joined endpoint to endpoint under a declared simplicity and interior convention.
• Prim’s Algorithm — A greedy minimum-spanning-tree algorithm that grows one connected tree from a chosen start vertex by repeatedly adding a cheapest edge crossing from the current tree to an unreached vertex.
• Prism graph — The cubic graph C_n □ K_2 of an n-gonal prism, formed by two n-cycles joined by matching cross-layer edges.
• Rigidity Matroid — The edge matroid represented by a framework's rigidity matrix, encoding independent first-order distance constraints and their rank in a fixed Euclidean dimension.
• Sierpiński Graph — A recursively structured graph whose word-labeled vertices connect by a first-difference and swapped-suffix rule.
• Total graph — A graph encoding both vertices and edges of a source graph, with adjacency for adjacency or incidence in the source.
• Utility graph — The complete bipartite graph K3,3, whose two sets of three vertices and nine cross-edges encode the nonplanar three-utilities puzzle.