Fact-checked by Grok 2 weeks ago

Permutation graph

A permutation graph is an undirected graph in the field of graph theory whose vertices correspond to the elements of a permutation \pi of the set \{1, 2, \dots, n\}, with an edge between distinct vertices i and j (assuming i < j) if and only if \pi(i) > \pi(j), meaning the pair forms an inversion in the permutation.^[1] Equivalently, permutation graphs are the intersection graphs of straight-line segments joining two parallel lines, where each segment connects position i on the first line to position \pi(i) on the second line, and two segments intersect if and only if their endpoints form an inversion.^[2] Permutation graphs are characterized by the property that both the graph and its complement are comparability graphs of partial orders, a result established by Pnueli, Lempel, and Even in 1971.^[2] This dual comparability implies that permutation graphs are perfect graphs, meaning their chromatic number equals the clique number for every induced subgraph, and they inherit efficient algorithms for optimization problems like coloring and clique finding from the broader class of perfect graphs.^[2] As a subclass of co-comparability graphs, they admit transitive orientations and modular decompositions that facilitate structural analysis.^[2] Recognition of permutation graphs can be performed in linear time O(n + m), where n is the number of vertices and m the number of edges, by finding transitive orientations of both the graph and its complement and constructing an intersection model, as refined by McConnell and Spinrad in 1999.^[2] Prime permutation graphs—those without non-trivial modules—possess a unique realizer up to reversal equivalences, a property tracing back to Gallai's work on transitive orientations in 1967.^[2] These graphs have found applications in areas such as scheduling problems,^[3] VLSI design,^[4] and distance labeling in distributed computing,^[1] where their inversion-based structure enables efficient representations and queries.

Definitions and Basic Concepts

Permutation-Based Definition

A permutation graph arises from a permutation \sigma = (\sigma_1, \sigma_2, \dots, \sigma_n) of the set \{1, 2, \dots, n\}. The graph G has vertex set \{1, 2, \dots, n\}, and an edge connects distinct vertices i and j (assuming without loss of generality i < j) if and only if \sigma^{-1}(i) > \sigma^{-1}(j), where \sigma^{-1}(k) is the position of k in \sigma.^[5] This setup encodes the relative ordering induced by the permutation into the graph's adjacency.^[6] In discrete mathematics, an inversion of a permutation \sigma is a pair of indices a < b such that \sigma(a) > \sigma(b).^[7] The edge condition \sigma^{-1}(i) > \sigma^{-1}(j) for i < j identifies pairs where the natural order of the values is reversed in their positions within \sigma, corresponding to inversions in the inverse permutation \sigma^{-1}.^[5] The total number of edges in G equals the inversion count of \sigma, denoted \operatorname{inv}(\sigma), which measures the extent of disorder in the permutation.^[5]^[8] For instance, take \sigma = (2, 1, 3). Here, \sigma^{-1}(1) = 2, \sigma^{-1}(2) = 1, and \sigma^{-1}(3) = 3. The pair i=1 < j=2 satisfies \sigma^{-1}(1) > \sigma^{-1}(2) (since $2 > 1), yielding an edge between 1 and 2; no other pairs meet the condition, so the graph consists of vertices 1, 2, 3 with a single edge \{1,2\}.^[5] This example has \operatorname{inv}(\sigma) = 1, matching the edge count.^[8] Permutation graphs were introduced by Gary Chartrand and Frank Harary in 1967.^[9]

Geometric Interpretation

A permutation graph can be defined geometrically as the intersection graph of a set of straight line segments, where each segment has one endpoint on a horizontal line at y=0 and the other on a parallel horizontal line at y=1, connecting the point (i, 0) to (σ(i), 1) for i = 1 to n, and σ is a permutation of {1, ..., n}.^[10] In this representation, the vertices of the graph correspond to the line segments, and an edge exists between two vertices if and only if their corresponding line segments intersect in the interior of the strip between the two lines. This geometric model provides an intuitive visualization of the graph's structure, distinct from its algebraic definition based on permutations. The intersections in this diagram occur precisely when two line segments cross, which happens if and only if the endpoints form an inversion in the permutation: for distinct i and j with i < j, the segments from (i, 0) to (σ(i), 1) and (j, 0) to (σ(j), 1) intersect if and only if σ(i) > σ(j).^[10] To see why, consider the geometry of straight lines between parallel horizontals: assuming the x-coordinates are ordered increasingly from left to right on both lines, a crossing requires the lower endpoints to be in one order (i < j) while the upper endpoints reverse that order (σ(i) > σ(j)). Non-crossing segments either nest or are disjoint without overlap, corresponding to non-inversions. For illustration, consider n=3 and the permutation σ = (2, 1, 3), so the segments are from (1, 0) to (2, 1), (2, 0) to (1, 1), and (3, 0) to (3, 1). The first two segments cross because 1 < 2 but σ(1)=2 > 1=σ(2), forming an edge between vertices 1 and 2; the third segment does not cross either, so vertices 1-3 and 2-3 have no edges. This yields a graph with a single edge, matching the inversion table of σ. This geometric representation is equivalent to the permutation-based definition because the set of intersections directly encodes the inversions of σ, and any permutation graph admits such a diagram where crossings are exactly the edges.^[10] The bipartition of endpoints into the two parallel lines ensures that all intersections are proper crossings within the strip, without endpoints coinciding or segments overlapping at boundaries.

Characterizations

Graph-Theoretic Characterizations

A graph G is a permutation graph if and only if both G and its complement \overline{G} are comparability graphs, meaning each admits a transitive orientation of its edges. This equivalence, which highlights the duality between permutation graphs and their complements, was proved by Pnueli, Lempel, and Even.^[11] As a consequence of this characterization, the class of permutation graphs is closed under taking complements: if G is a permutation graph, then so is \overline{G}, since the roles of G and \overline{G} are symmetric in the definition. In his seminal work, Gallai provided a structural theorem describing the decomposition of graphs that are both comparability graphs and co-comparability graphs (i.e., permutation graphs), expressing them as compositions of certain irreducible components under disjoint union and join operations.^[12] Additionally, Gallai established a forbidden induced subgraph characterization for permutation graphs, identifying an infinite family of minimal forbidden subgraphs that arise from violations of transitive orientability in either the graph or its complement.^[12]

Poset and Dimension Characterizations

Permutation graphs admit an order-theoretic characterization in terms of partial orders (posets) and their dimensions. Specifically, a graph is a permutation graph if and only if it is the comparability graph of a poset whose order dimension is at most 2. The comparability graph of a poset has vertices corresponding to the elements of the poset, with an edge between two vertices if the corresponding elements are comparable (either one precedes the other or vice versa). This equivalence establishes a direct link between the intersection model of permutation graphs and the structure of low-dimensional posets. The order dimension of a poset P, denoted \dim(P), is defined as the smallest integer d such that P can be expressed as the intersection of d linear extensions of P. A linear extension of P is a total order on the elements of P that respects all the ordering relations in P. Thus, for \dim(P) \leq 2, there exists a realizer consisting of exactly two linear extensions L_1 and L_2 such that x < y in P if and only if x precedes y in both L_1 and L_2. This binary realization aligns with the permutation model of such graphs, where the two linear extensions can be viewed as the top-to-bottom and left-to-right orders in a permutation diagram, and the resulting comparability relations capture the intersections of line segments between them. In this context, the dimension-2 condition corresponds to the underlying permutation avoiding certain forbidden patterns that would require additional linear extensions for realization. Trotter, Moore, and Sumner (1976) provided key insights into this characterization, demonstrating that the comparability graphs of dimension-2 posets precisely coincide with permutation graphs and establishing foundational results on their structural properties.^[13] Their work highlighted how the restriction to two dimensions ensures the graph admits a transitive orientation compatible with the permutation representation, without introducing higher-dimensional complexities. Bipartite permutation graphs form an important subclass in this framework. While dimension-1 posets are disjoint unions of chains (yielding comparability graphs that are disjoint unions of cliques), the focus on dimension 2 captures the full class of permutation graphs, including bipartite ones, which arise from height-2 posets with the two-partite structure enforced by the bipartition. This connection underscores the role of dimension 2 as the threshold for the permutation property in comparability graphs.

Recognition and Construction Algorithms

Linear-Time Recognition

Permutation graphs can be recognized in linear time by leveraging their characterization as the intersection of comparability graphs and co-comparability graphs. To determine membership, an algorithm first tests whether the input graph admits a transitive orientation, confirming it as a comparability graph, and then performs an analogous test on the graph's complement to verify co-comparability. This dual testing approach exploits the structural properties derived from order dimension theory, where permutation graphs correspond to partial orders of dimension at most two.^[14] A seminal linear-time algorithm for this recognition was developed by McConnell and Spinrad, achieving O(n + m) time complexity, where n is the number of vertices and m is the number of edges. The method relies on efficient transitive orientation procedures, which orient the edges to form a transitive digraph if the graph is comparability; the same process is applied to the complement for co-comparability verification. If both succeed, the graph is a permutation graph; otherwise, a certificate of non-membership (such as an asteroidal triple or forbidden substructure) can be produced. This algorithm builds on prior work in modular decomposition to handle the orientation efficiently without explicit complement construction, avoiding quadratic overhead.^[15] The recognition process begins by computing a modular decomposition of the input graph, which identifies prime and decomposable modules in linear time. For the comparability test, the algorithm attempts a transitive orientation starting from a lexicographic breadth-first search (LexBFS) ordering to guide the edge directions, ensuring transitivity by verifying closure under the partial order. If successful, it produces a transitive orientation; failure indicates non-comparability via an induced path of length three without a chord. The co-comparability test follows identically on the implicit complement, using adjacency checks to simulate edges in the complement without materializing it. This step-wise verification confirms the graph's membership while maintaining the overall linear bound. The correctness of the algorithm hinges on the use of modular decomposition to reduce the problem to prime subgraphs, where transitive orientations are unique up to reversal for permutation graphs. Prime graphs are tested directly via the orientation procedure, ensuring no false positives, as the decomposition preserves the comparability and co-comparability properties across modules. This decomposition-based reduction guarantees that the recognition is both complete and sound, with the transitive orientations serving as certificates for affirmative instances. Subsequent certifying variants, such as those by Habib et al., extend this framework to provide explicit proofs of membership or non-membership in linear time.^[16]^[14]

Permutation Reconstruction

Once a graph G has been recognized as a permutation graph, the underlying permutation \sigma can be reconstructed by first computing transitive orientations of G and its complement \bar{G}. A transitive orientation D of G orients the edges such that if there is a directed path from u to v, then there is a direct edge from u to v; the same applies to the orientation \bar{D} of \bar{G}. This characterization stems from the fact that a graph is a permutation graph if and only if both it and its complement admit transitive orientations. The reconstruction proceeds by deriving two linear extensions from these orientations to form a dimension-2 realizer of the underlying partial order. Specifically, perform a topological sort on the union of D and \bar{D} to obtain the first linear extension \pi_1, which orders the vertices according to the combined constraints. Then, perform a topological sort on the union of the reverse of D (i.e., flipping all directions in D) and \bar{D} to obtain the second linear extension \pi_2. These \pi_1 and \pi_2 represent the orderings of the endpoints on the two parallel lines in the geometric model of the permutation graph. To construct \sigma, label the vertices according to their positions in \pi_1 (assigning labels 1 through n in that order), and then determine \sigma(i) as the position of label i in \pi_2. This yields the permutation where edges correspond to inversions in \sigma. The resulting model can be verified by checking that segments connecting corresponding points in \pi_1 and \pi_2 intersect precisely when there is an edge in G.^[17] For connected prime permutation graphs—those that are not decomposable into parallel or series modules—the reconstructed permutation is unique up to reversal of the order and relabeling of the vertices. This uniqueness follows from Gallai's theorem on the structure of 2-dimensional partial orders, where the realizer is essentially unique up to reversal for irreducible cases. In general graphs, modular decomposition is used to recursively reconstruct the permutation by combining the unique realizers of prime components, ensuring the overall labeling is consistent across modules.^[17] The entire reconstruction process, integrated with the recognition algorithm, runs in O(n + m) time, where n is the number of vertices and m is the number of edges, by leveraging efficient modular decomposition and topological sorting.^[14]

Properties and Optimization

Perfect Graph Properties

A graph is perfect if, for every induced subgraph H, the chromatic number \chi(H) equals the clique number \omega(H). This property ensures that coloring and clique problems align optimally across all induced subgraphs, making perfect graphs central to optimization in graph theory. Permutation graphs form a subclass of comparability graphs, which are the undirected graphs admitting a transitive orientation corresponding to a partial order.^[18] Comparability graphs are perfect, as established by Mirsky's theorem, which equates the chromatic number to the size of the maximum clique via the height of the associated poset (the length of the longest chain). Consequently, permutation graphs inherit this perfection, satisfying \chi(G) = \omega(G) for every induced subgraph G. As perfect graphs, permutation graphs contain no induced odd holes (chordless cycles of odd length greater than 3) or odd anti-holes (complements of such cycles).^[19] This structural implication follows from the Strong Perfect Graph Theorem, which characterizes perfect graphs as precisely the Berge graphs free of these forbidden subgraphs; although permutation graphs were recognized as perfect decades earlier, the theorem provides a broader forbidden-subgraph characterization relevant to their structure.^[19]

Efficiently Solvable Problems

Permutation graphs, as a subclass of perfect graphs, enable the efficient solution of several classical optimization problems that are NP-hard in general graphs, due to their structural properties such as comparability and representation via permutations.^[20] Specifically, graph coloring, maximum clique, and maximum independent set can all be solved in polynomial time, often leveraging the permutation representation or auxiliary structures like PQ-trees for dynamic programming approaches.^[21] The minimum graph coloring problem on permutation graphs can be solved in linear time, O(n + m), by first obtaining a transitive orientation of the graph, which corresponds to a two-dimensional partial order, and then coloring vertices along this partial order using a greedy algorithm on a linear extension.^[22] This approach exploits the fact that the chromatic number equals the size of the maximum clique, and the orientation allows topological processing to assign colors without conflicts. An alternative O(n log n)-time method decomposes the permutation into the minimum number of increasing subsequences, equivalent to chain partitioning in the associated poset.^[21] The maximum clique problem is solvable in O(n log n) time by identifying the longest decreasing subsequence in the defining permutation, as cliques correspond to sets of elements forming such subsequences in the inversion model.^[23] Similarly, the maximum independent set problem reduces to finding the longest increasing subsequence in the permutation, which can be computed using patience sorting or dynamic programming in O(n log n) time, since independent sets represent non-inverted pairs. These reductions highlight how the permutation model facilitates divide-and-conquer or dynamic programming strategies directly on the sequence. The existence of a Hamiltonian path in a permutation graph can be determined and constructed in O(n^2) time using layer-based dynamic programming on the permutation diagram, checking for follow-up vertices in the lowest layer to ensure traceability.^[24] Additionally, the minimum feedback vertex set problem, which seeks the smallest set of vertices whose removal makes the graph acyclic, is solvable in polynomial time, with early algorithms achieving O(n^6) via integer programming on the poset structure, later improved to O(n m) using dynamic programming.^[25] These efficiencies stem from the graph's bounded dimension and transitive properties, avoiding the exponential search required in general graphs.

Relations to Other Graph Classes

Superclasses and Inclusions

Permutation graphs form a subclass of circle graphs, which are defined as the intersection graphs of chords on a circle. In particular, every permutation graph arises as a circle graph with a representation featuring an "equator" chord that intersects every other chord in the model.^[26] They are also a subclass of trapezoid graphs, the intersection graphs of trapezoids aligned between two parallel horizontal lines. This inclusion extends the geometric representation of permutation graphs as intersections of horizontal line segments between two parallels, allowing for trapezoids with non-parallel slanted sides.^[26] As co-comparability graphs, permutation graphs have complements that are comparability graphs of transitive orientations.^[14] This property positions them within the class of perfect graphs, where the chromatic number equals the clique number for every induced subgraph.^[27] Kratsch, McConnell, Mehlhorn, and Spinrad established linear-time certifying algorithms for recognizing permutation graphs, leveraging their structure within co-comparability and related superclass frameworks.^[14]

Subclasses and Examples

Bipartite permutation graphs form a significant subclass of permutation graphs, consisting of those permutation graphs that are bipartite. These graphs are characterized by the property that their biadjacency matrix can be arranged to exhibit the consecutive-ones property for rows and columns, enabling efficient recognition algorithms.^[28] They also admit a strong ordering of the partite sets where adjacency and enclosure conditions hold.^[29] Within this subclass, bipartite threshold graphs emerge as a further refinement, representing the intersection of bipartite permutation graphs and threshold graphs, which maintain additional structural simplicity such as being free of certain induced subgraphs.^[30] Cographs, defined as P_4-free graphs constructed via disjoint unions and joins of isolated vertices, constitute another key subclass of permutation graphs. These graphs correspond precisely to the permutation graphs generated by separable permutations, which avoid certain crossing patterns in their models.^[31] Threshold graphs, characterized by their degree sequences and lack of induced P_4, C_4, or $2K_2 subgraphs, also form a subclass of permutation graphs; notably, their adjacency matrices possess the consecutive-ones property when rows and columns are suitably ordered, reflecting a nested structure in the permutation representation.^[31] Representative examples illustrate these subclasses effectively. The complete graph K_n is a permutation graph, arising from the reverse permutation \pi(i) = n+1-i, where every pair of segments intersects.^[6] Disjoint unions of cliques are permutation graphs, as they belong to the cograph subclass and can be realized through modular decompositions that preserve the permutation model.^[31] Threshold graphs exemplify permutation graphs with the consecutive-ones property in their adjacency matrices, often modeling dominance orders in social networks or resource allocation.^[31]

References

[1]
[PDF] Optimal Distance Labeling for Permutation Graphs - arXiv
Jul 16, 2024 · A permutation graph is the intersection graph of a set of segments between two parallel lines. In other words, they are defined by a permutation ...
[2]
[PDF] Permutation graphs --- an introduction
Theorem ([Pnueli, Lempel, Even '71], see also [Golumbic '80]). G is a permutation graph if and only if G and G are comparability graphs. Algorithm.
[3]
https://www.sciencedirect.com/science/article/pii/S0890540102000287
[4]
Permutation Graph -- from Wolfram MathWorld
For a permutation alpha in the symmetric group S_p, the alpha-permutation graph of a labeled graph G is the graph union of two disjoint copies of G (say, ...
[5]
[PDF] Permutation Graphs
- if we succeed in finding transitive orientations, then the graph is a permutation grape. • To find a suitable permutation we can follow the construction ...
[6]
[PDF] MAT022A University of California, Davis Winter 2000 Lecture Notes ...
If the permutation is represented by its action on 1, 2, . . . , n, an inversion is just a pair that appears in decreasing order in the list π&% , π(' , . . . , ...
[7]
[PDF] 7. Permutations
Definition. A permutation is an ordering or the numbers 1 through N. student ... An inversion in a permutation is the number of pairs i j with i > j.
[8]
[PDF] Planar Permutation Graphs - Numdam
Planar Permutation Graphs (1). Gary CHARTRAND and Frank HARARY. INTRODUCTION. Ann. Inst. Henri Poincaré,. Vol. III, n° 4, 1967, p. 438. Section B : Calcul des ...
[9]
Algorithmic graph theory and perfect graphs - Internet Archive
May 31, 2023 · Algorithmic graph theory and perfect graphs. by: Golumbic, Martin Charles. Publication date: 1980. Topics: Graph theory. Publisher: New York ...
[10]
Transitiv orientierbare Graphen - Semantic Scholar
In this paper, we introduce Euclidean Gallai-Ramsey theory, by combining Euclidean Ramsey theory and Gallai-Ramsey theory on graphs. More precisely, we ...
[11]
Certifying Algorithms for Recognizing Interval Graphs ... - SIAM.org
We give linear-time certifying algorithms for recognition of interval graphs and permutation graphs, and for a few other related problems. Previous ...
[12]
Linear-time transitive orientation | Proceedings of the eighth annual ...
Linear-time modular decomposition and efficient transitive orientation of comparability graphs. ... This paper presents an algorithm for the transitive ...
[13]
[PDF] Linear-Time Modular Decomposition and Efficient Transitive ...
The transitive orientation problem is the problem of orienting the edges of a comparability graph so that the result is a partial order. If such an orientation ...
[14]
[PDF] Certifying Algorithms for Recognizing Interval Graphs and ...
We give linear-time certifying algorithms for recognition of interval graphs and permutation graphs. Previous algorithms fail to provide supporting evidence of ...
[15]
TRANSITIVE ORIENTATION OF GRAPHS AND IDENTIFICATION ...
In § 3 we show that a graph G is a permutation graph if and only if both G and its complement Gc are TRO. (Gc is a graph with the same vertices as G and two ...Missing: citation | Show results with:citation
[16]
[PDF] The strong perfect graph theorem - Annals of Mathematics
, and AIM. Page 2. 52. M. CHUDNOVSKY, N. ROBERTSON, P. SEYMOUR, AND R. THOMAS the chromatic number of H equals the size of the largest clique of H. The study ...
[17]
The complexity of comparability graph recognition and coloring
Using the notion ofG-decomposition introduced in Golumbic [8, 9], we present an implementation of an algorithm which assigns a transitive orientation to a ...
[18]
Decomposing a set of points into chains, with applications to ...
This result is then used to derive O(n log n) time algorithms for a number of problems concerning permutation graphs, including minimum coloring—thus improving ...
[19]
[PDF] Linear-Time Transitive Orientation - Colorado State University
A linear time bound follows from Proposition 1.1. Verifying that the graph is a permutation graph thus reduces to verifying that the intersection of the ...<|control11|><|separator|>
[20]
Permutation Graphs and Transitive Graphs | Journal of the ACM
PNUELI, A., LEMPEL, A., AND EVEN, S. Transitive orientation of graphs and identification of permutation graphs. Canad. J. Malh. 23 (1971), 160 175. Google ...
[21]
Hamiltonian path in permutation graphs - ScienceDirect
Aug 28, 2025 · The existing best algorithm for the Hamiltonian path problem in a permutation graph requires O ( n 2 ) time.
[22]
On the feedback vertex set problem in permutation graphs
Brandstädt and Kratsch (1987) presented an O(n6) time algorithm for the minimum weight feedback vertex set problem in a permutation graph of n vertices and ...
[23]
[PDF] Trapezoid Graphs and Generalizations, Geometry and Algorithms
Trapezoid graphs are a class of cocomparability graphs containing interval graphs and permutation graphs as subclasses. They were introduced by Dagan, Golumbic ...Missing: superclasses | Show results with:superclasses
[24]
Permutation graphs - ScienceDirect.com
An undirected graph G is called a permutation graph if there exists a permutation π such that G ≅ G[π].
[25]
Bipartite permutation graphs - ScienceDirect.com
This paper examines the class of bipartite permutation graphs. Two characterizations of graphs in this class are presented.
[26]
bipartite permutation - Graph Classes
A bipartite graph G = (A, B, E) is a bipartite permutation graph iff it admits an ordering of A that has the adjacency and enclosure properties.
[27]
[PDF] Computing the cutwidth of bipartite permutation graphs in linear time*
They present two characterizations of bipartite permutation graphs, leading to a linear-time recognition algorithm for this class as well as polynomial-time ...
[28]
Enumerative aspects of certain subclasses of perfect graphs
For subclasses of permutation graphs like cographs and threshold graphs we also determine the number of permutations π of {1,2,…,n} such that the permutation ...
[29]
Canonical Antichains of Unit Interval and Bipartite Permutation Graphs
Nov 13, 2010 · We study unit interval graphs and bipartite permutation graphs partially ordered by the induced subgraph relation.
[30]
Advances on sorting by reversals - ScienceDirect.com
Apr 1, 2007 · Sorting a signed permutation π by reversals involves two successive procedures on what is called the overlap graph of π . The first one consists ...