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 whose edges join exactly the pairs that are comparable in some partial order. Equivalently, there exists a way to direct all its edges so that the resulting directed relation is transitive: if \(a\to b\) and \(b\to c\), then edge \(ac\) is present and directed \(a\to c\). The undirected graph is the object being classified; a transitive orientation is a witness of membership and may not be unique.[1][2]
This is the full order shadow, not merely the graph of immediate cover relations. For a chain \(a<b<c\), its comparability graph has \(ab\), \(bc\) and \(ac\). A Hasse diagram would usually draw only the two covers. Algorithms that find an orientation, and theorems about graph perfection or optimization, are uses or consequences; none is another constitutive role.[1]
Structural Signature¶
Sig role-phrases: undirected vertices and edges → all comparable-pair adjacency → existence of a transitive orientation.
- Undirected graph object. Vertices and unordered edges supply the connection pattern. One chosen arrow assignment is not built into the graph's identity.[1]
- All comparable-pair adjacency. Some strict partial order must make an edge correspond to each comparable pair, including pairs implied through intermediate vertices. A cover-only drawing omits such edges.[1]
- Transitive-orientation existence. Every edge can be directed so that two consecutive arrows force the implied forward edge. If no such orientation exists, the graph is not in the class.[1][2]
One algorithm, a unique order, a perfect-graph theorem and a scheduling interpretation are not necessary roles.
What It Is Not¶
A comparability graph is not a partially ordered set itself. The order gives arrow directions and incomparable pairs; the graph forgets direction while retaining adjacency of comparable pairs. It is not one selected transitive orientation either—an undirected graph can admit different witnesses. Nor is it generally a cover graph: the three-element chain's endpoint edge is necessary in its comparability graph even when omitted from a Hasse diagram.[1]
It is also not every network or graph with a plausible hierarchy drawn on it. The full edge set must support a transitive orientation. Live Transitive Relation is a related directed relation; it is not the same undirected object. Recognition algorithms and complexity bounds should be kept separate from this class definition.[1][2]
Scope of Application¶
Order theory supplies direct examples: on a selected finite set of positive integers, direct an edge from (a) to (b) when (a) divides (b) and (a\ne b). Divisibility is transitive, and the undirected comparable-pair graph therefore meets the test. The three vertices 2, 4 and 8 form a triangle of comparable pairs even though a compact cover drawing might show only 2–4–8.[1]
Precedence among tasks can also define an order. If task A must precede B and B must precede C, the comparability graph includes AC as well as AB and BC. This uses the transitive closure of precedence comparabilities, not merely the immediate-prerequisite arrows. Tedder's original paper identifies scheduling as an application area, but this three-task instance is a constructed illustration of the definition, not a claim about a particular scheduler.[2]
Clarity¶
The transitivity test is about oriented edges and their forced closure, not about every two-edge undirected path. A vertex triple can have two incident edges pointing both inward; then the two-step premise does not arise. Conversely, once a directed two-step path does arise, the endpoint edge must exist and have the compatible direction.[1]
One may be given a graph already known to be comparability and asked to find an orientation, or be given an arbitrary graph and asked whether any such orientation exists. Tedder's linear-time result is stated for finding an orientation of a comparability graph; it should not be quoted without qualification as a linear-time recognition theorem for arbitrary inputs.[2]
Manages Complexity¶
The class permits order reasoning on an undirected connection object. Cliques correspond to mutually comparable vertices under an associated orientation, while missing edges indicate incomparability. An orientation witness can expose chains and precedence relations without changing the underlying graph. This is representational economy, not a guarantee that a particular orientation or algorithm is uniquely determined.[1][2]
Abstract Reasoning¶
To decide whether a graph is comparability, seek a direction for every edge and test transitivity. A proposed order must account for every graph edge and for every pair it makes comparable; a three-chain with a missing endpoint edge is not a valid witness. To understand a graph after admission, distinguish claims invariant under all valid orientations from claims made about one chosen order.[1]
If a solver takes a known comparability graph and outputs arrows, that is constructive orientation. If it takes an arbitrary graph and decides membership, that is recognition. An algorithm may address one or both, but the complexity claim must state its input promise.[2]
Knowledge Transfer¶
Divisibility and task precedence are unlike relations, yet each can produce an undirected edge exactly when two elements are ordered relative to one another. The same three roles map: vertices, all comparable-pair adjacency and a transitive orientation witness. The live Network prime carries the broader node-edge skeleton; comparability graphs add a specific order-shadow condition. This does not make all task-dependency diagrams comparability graphs—cover-only diagrams need closure first.[1][2]
Examples¶
Divisibility on 2, 4 and 8. The undirected graph has those three number vertices. Its comparable-pair adjacency includes 2–4, 4–8 and 2–8, because each earlier number divides each later one. The orientation witness is \(2\to4\to8\) together with \(2\to8\), satisfying transitivity. The triangle is the order shadow, not just a chain drawing.[1]
Mapped back: the transitive endpoint edge fills the all-pairs role and prevents confusion with a cover graph.
Three-task precedence. Let A precede B and B precede C. The graph has task vertices A,B,C; its adjacency must include AB, BC and AC because A also precedes C; its orientation sends A to B, B to C and A to C. This is a constructed scheduling instance of the definition, not an assertion that every real prerequisite diagram already includes its closure.[2]
Mapped back: tasks replace integers, but the edge-closure and orientation-existence test remains exact.
Negative boundary. Draw only AB and BC for that same task order. This is a valid cover diagram of the chain, but it omits AC and is not the comparability graph of that three-element chain. Another orientation might make the undirected path a comparability graph of a different poset, so the negative claim is about the given order-shadow mapping rather than intrinsic nonmembership of the three-vertex path.[1]
Structural Tensions¶
- Undirected economy versus order recovery. Forgetting directions keeps a graph-level object that may admit multiple orders; choosing an orientation recovers one order but adds a witness-dependent interpretation. Diagnostic: Is the claim invariant under all transitive orientations, or does it depend on a selected one?[1]
- Cover sparsity versus full comparable-pair adjacency. A Hasse diagram hides implied relations for compactness, while the comparability graph includes every comparable pair and can be denser. Diagnostic: When A precedes B and B precedes C, has the endpoint AC pair been represented in the object actually called the comparability graph?[1]
- Orientation guarantee versus recognition cost. Knowing class membership lets an algorithm focus on producing an orientation; arbitrary-input recognition must also decide whether such a witness exists. Conflating these promises overstates a complexity result. Diagnostic: Does the theorem assume comparability on input or certify it?[2]
Structural–Framed Character¶
Comparability Graph is strongly structural within graph and order theory: its edge set either admits a transitive orientation or it does not. Its evaluative weight is neutral; membership does not say the represented order is fair, useful or true of a real system. Its human-practice dependence lies in choosing vertices and what “precedes” or “divides” means, whereas the orientation criterion is mathematically determined. Its institutional origin is graph theory, not a convention enforced by an organization. Its vocabulary travel reaches divisibility and scheduling because both literally yield comparable-pair graphs, but not every sparse dependency sketch. Import versus recognition requires all implied comparable edges and an orientation witness, not a verbal claim that a diagram depicts an order.
Live Network supplies the portable node-edge skeleton across substrates; this child adds undirected order-shadow adjacency and transitivity of a possible direction assignment. Its character: a formal graph class with meaningful cross-setting instantiation but a specific order-theoretic membership test.
Structural Core vs. Domain Accent¶
What is skeletal. A node set and pairwise edges are studied as a connection pattern independent of substrate. Live Network is the proposed strict parent. Comparability Graph inherits that object and constrains its edge set by a possible transitive orientation; Transitive Relation is a related witness structure, not the graph-level genus.
What is domain-bound. Edges must be precisely the comparable unordered pairs of some strict partial order, including transitive pairs, while a choice of arrow orientation may vary. Numbers/divisibility and tasks/precedence are setting accents. Remove the order-shadow condition and the object is merely a graph; replace all-pairs adjacency with cover-only edges and it ceases to be the same graph of that chosen order.
Why this is not a prime. Network travels among social, biological and technological connections without requiring partial orders. Comparability Graph is recognized only when undirected adjacency admits the exact transitive-orientation test. Applying the phrase to any network with “comparable-looking” nodes would import vocabulary without the defining order relation. The more portable node-edge idea is already live as a prime.
Instantiates / Related Primes¶
This entry is a kind of Network.
DAG parent: live Network (Network). A comparability graph is an undirected node-edge network subject to an additional order constraint. Live Transitive Relation is a possible directed orientation relation, not the child graph itself. A cover graph is another representation of a poset and cannot be substituted without adding implied comparable edges for that order.
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.Live Network defines a node set and connection pattern independent of substrate. A comparability graph is such an undirected node-edge pattern, restricted to edges that can be oriented as the comparable-pair relation of a strict partial order. The orientation is a witness, not the child graph's fixed identity.
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
Not to Be Confused With¶
- Transitive orientation. It is an assignment of directions proving graph membership, not the undirected graph. Tell: are arrows part of the object or a witness?[1]
- Hasse/cover graph. It retains immediate covers but omits transitive pairs. Tell: does a three-element chain include the endpoint edge in the claimed graph?[1]
- Recognition versus orientation algorithm. One decides arbitrary-input membership; the other may assume membership and output arrows. Tell: what input promise does the complexity theorem state?[2]
References¶
[1] 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 and transitive-orientation construction. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r
[2] Marc Tedder, "Simpler, Linear-Time Transitive Orientation via Lexicographic Breadth-First Search", original paper (2015), abstract and §§1–2. The stated linear-time claim concerns finding an orientation of a known comparability graph. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k