Permutation Graph Checker

inversion graph of π

CheckersFreeNo Signup
4.3(620 reviews)
All Tools

Loading tool...

About Permutation Graph Checker

A permutation graph checker testing if G arises from a permutation π: vertices i,j adjacent iff i<j but π(i)>π(j) (inversion). Equivalently: intersection graph of line segments between two parallel lines. Perfect, comparability ∩ co-comparability. Client-side.

Permutation Graph Checker Features

  • Permutation test
  • Find π
  • Inversions
  • Perfect
  • O(n+m)
Permutation graph: from permutation π of {1,...,n}, vertices i,j adjacent iff they form an inversion (iπ(j)). Equivalently: intersection graph of line segments connecting points on two parallel lines. comparability ∩ co-comparability = permutation.

How to Use

Select graph:

  • Test: Permutation?
  • π: Find permutation
  • Inversions: Edge list

Inversions

An inversion of π: pair (i,j) with iπ(j). Total inversions = |E|. Sorting = resolving inversions. The number of inversions measures 'disorder'. Merge sort counts inversions in O(n log n).

Recognition

G is permutation iff both G and Ḡ are comparability graphs. O(n+m) via modular decomposition + transitive orientation of G and Ḡ simultaneously. Also: LBFS-based algorithms.

Step-by-Step Instructions

  1. 1Select graph.
  2. 2Check permutation.
  3. 3Find π.
  4. 4Count inversions.
  5. 5Solve problems.

Permutation Graph Checker — Frequently Asked Questions

Which graphs are permutation graphs?+

Path P_n: always permutation (π = reverse). Cycle C_n (n≥5): NOT permutation. Complete K_n: permutation (π = reverse). Bipartite: some are (K_{m,n} yes), some aren't. Trees: always permutation if caterpillar.

What's the line segment model?+

Draw n points on top line and n points on bottom line. Connect point i (top) to point π(i) (bottom). Two segments cross iff the corresponding vertices are adjacent. Crossings = inversions!

What's longest increasing subsequence?+

LIS of π = maximum independent set of the permutation graph. LIS length = α(G). By Dilworth: also equals minimum number of decreasing subsequences covering π. Solvable in O(n log n).

More Checkers Tools

Explore all 223 other checkers tools available on Generatr

Academic Readability Graderads.txt ValidatorAI Content DetectorAlexander McQueen Serial Number CheckerAnagram CheckerAnalog Gem Tester SimulatorAnsible LinterArc-Transitive Graph CheckerAudemars Piguet Serial Number CheckerAuto Parts Compatibility CheckerBike Serial Number CheckerBlocked Checker TwitterBluesky Block CheckerBottega Veneta Serial Number CheckerBrawl Stars Mastery CheckerBulk SERP CheckerBulova Serial Number CheckerCanned Phrase & Cliche CheckerCar Stereo Compatibility CheckerCartier Love Bracelet Serial Number CheckerCartier Serial Number CheckerCeline Serial Number CheckerCetaphil Lot Number CheckerCGC Certification LookupCharacter Frequency CounterChordal Graph CheckerCircleboom Shadowban CheckerClash Royale Deck CheckerClash Royale Synergy CheckerCograph Recognition Checker
View all 223 checkers tools
Share this tool: