An Algorithm for Hinge Vertex Problem on Circular Trapezoid Graphs

Let G = (V, E) be a simple connected graph. A vertex u ∈ V is called a hinge vertex if there exist two vertices x and y in G whose distance increases when u is removed. Finding all hinge vertices of a given graph is called the hinge vertex problem. This problem can be applied to improve the stability and robustness of communication network systems. In a number of graph problems, it is known that more efficient sequential or parallel algorithms can be developed by restricting classes of graphs. Circular trapezoid graphs are proper super-classes of trapezoid graphs. In this paper, we propose an O(n2) time algorithm for the hinge vertex problem of circular trapezoid graphs.