A hinge vertex is a vertex in an undirected graph such that there exist two vertices whose removal makes the distance between them longer than before. Identifying hinge vertices in a graph can help detect critical nodes in communication network systems, which is useful for making them more stable. For finding them, an O(n3) time algorithm was developed for a simple graph, and, linear time algorithms were developed for interval and permutation graphs, respectively. Recently, the maximum detour hinge vertex problem is defined by Honma et al. For a hinge vertex u in a graph, the detour degree of u is the largest value of distance between any pair of x and y (x and y are adjacent to u) by removing u. A hinge vertex with the largest detour degree in G is defined as the maximum detour hinge vertex of G. This problem is motivated by practical applications, such as network stabilization with a limited cost, i.e., by enhancing the reliability of the maximum detour hinge vertex, the stability of the network is much improved. We previously developed an O(n2) time algorithm for solving this problem on an interval graph. In this study, we propose an algorithm that identifies the maximum detour hinge vertex on a permutation graph in O(n2) time, where n is the number of vertices in the graph.

Consider a simple undirected graph G = (V,E) with vertex set V and edge set E. Let G-u be a subgraph induced by the vertex set V-{u}. The distance δG(x,y) is defined as the length of the shortest path between vertices x and y in G. The vertex u ∈ V is a hinge vertex if there exist two vertices x,y ∈ V-{u} such that δG-u(x,y)>δG(x,y). Let U be a set consisting of all hinge vertices of G. The neighborhood of u is the set of all vertices adjacent to u and is denoted by N(u). We define d(u) = max{δG-u(x,y) | δG-u(x,y)>δG(x,y),x,y ∈ N(u)} for u ∈ U as detour degree of u. A maximum detour hinge vertex problem is to find a hinge vertex u with maximum d(u) in G. In this paper, we proposed an algorithm to find the maximum detour hinge vertex on an interval graph that runs in O(n2) time, where n is the number of vertices in the graph.