Comparability Graph¶
Join exactly the comparable pairs of a partial order in an undirected graph, equivalently requiring that its edges admit a transitive orientation.
Core Idea¶
A comparability graph is an undirected graph joining every pair of elements comparable in some partial order. Equivalently, its edges can be directed to make a transitive relation: \(a\to b\) and \(b\to c\) require edge \(ac\) directed \(a\to c\). The graph is the undirected object; a selected orientation witnesses membership and need not be unique.[ref-3cb3496af236][ref-d86ee467311e]
Scope of Application¶
Divisibility on 2, 4 and 8 yields all three edges because 2 divides 4 and 8, and 4 divides 8. A three-task precedence chain similarly yields AB, BC and AC when every comparable pair is represented. These are constructed examples of one role pattern, not claims that every sparse task-dependency sketch has already included its transitive closure.[ref-3cb3496af236][ref-d86ee467311e]
Clarity¶
A Hasse or cover graph draws immediate relations and can omit the endpoint edge of a three-element chain. Its comparability graph for that same order must include the endpoint edge. The cover-only three-vertex path may nevertheless be a comparability graph of a different order, so the distinction is about what relation its edges represent. A transitive orientation and recognition of an arbitrary graph are separate computational tasks.[ref-3cb3496af236][ref-d86ee467311e]
Manages Complexity¶
The graph retains order-comparability adjacency while suppressing a particular choice of directions. A compatible orientation can be produced when needed for chain or scheduling reasoning. An algorithm for orienting an input already known to be comparability should not be presented without qualification as arbitrary-input recognition.[^ref-d86ee467311e]
Abstract Reasoning¶
Seek directions for all edges and check that every directed two-step path has its forward endpoint edge. If no such assignment exists, the graph is outside the class. Live Network is the proposed strict genus because it supplies nodes and edges; live Transitive Relation describes a possible witness relation, not the undirected graph identity.[^ref-3cb3496af236]
Knowledge Transfer¶
Number divisibility and task precedence have different meanings, yet both can supply vertices, every comparable-pair edge and a transitive orientation. The named graph class transfers under that exact test, not merely when a drawing looks hierarchical.[ref-3cb3496af236][ref-d86ee467311e]
[^ref-3cb3496af236]: Dexter C. Kozen, Umesh V. Vazirani and Vijay V. Vazirani, "NC Algorithms for Comparability Graphs, Interval Graphs, and Unique Perfect Matchings", original author-hosted paper, §3 Definition 4. [^ref-d86ee467311e]: Marc Tedder, "Simpler, Linear-Time Transitive Orientation via Lexicographic Breadth-First Search", original paper (2015), abstract and §§1–2.
Relationships to Other Abstractions¶
Current abstraction Comparability Graph Domain-specific
Parents (1) — more general patterns this builds on
-
Comparability Graph is a kind of Network Prime
A comparability graph is a node-and-edge network with the extra condition of a transitive edge orientation.
Hierarchy path (1) — routes to 1 parentless root
- Comparability Graph → Network → Reservoir-Flux Network → Conservation Laws → Invariance
Neighborhood in Abstraction Space¶
Comparability Graph sits in a moderately populated region (53rd percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.
Family — Graph Structures & Combinatorial Objects (44 abstractions)
Nearest neighbors
- Induced Path — 0.86
- Connected Dominating Set — 0.86
- Hadwiger number — 0.86
- Two-Terminal Series–Parallel Graph — 0.86
- Biconnected Component — 0.85
Computed from structural-signature embeddings · 2026-10-08