Efficient algorithm for the vertex connectivity of trapezoid graphs

The intersection graph of a collection of trapezoids with corner points lying on two parallel lines is called a trapezoid graph. These graphs and their generalizations were applied in various fields, including modeling channel routing problems in VLSI design and identifying the optimal chain of non-overlapping fragments in bioinformatics. Using modified binary indexed tree data structure, we design an algorithm for calculating the vertex connectivity of trapezoid graph G   with time complexity O(nlogn), where n is the number of trapezoids.

► Trapezoid graph is an intersection graph of a collection of trapezoids. ► We design efficient algorithm for the vertex connectivity of trapezoid graphs. ► Time complexity is reduced from O(n2)O(n2) to O(nlogn) using efficient modified binary indexed tree data structure.