Center of Trapezoid Graph: Application in Selecting Center Location to Set up a Private Hospital

The central location problem is a key aspect of graph theory, with a significant importance in various applications and studies within the field. The center of a graph is made up of nodes that have the smallest eccentricity, where eccentricity is defined as the greatest distance between a given node and any other node in the graph. To determine the graph’s center, it is essential to compute the eccentricity of each node. In this article, we explore various characteristics of the BFS tree of trapezoid graphs. We also present new properties that relate to the radius, diameter, and center of trapezoid graphs. For the trapezoid graph G , We prove that the difference between the d i a m e t e r ( G ) and the height of the BFS trees T t ( 1 ) , T t ( n ) , T t ( a ) , and T t ( b ) is at most one. We also establish relationship between r a d i u s ( G ) and d i a m e t e r ( G ) of trapezoid graphs. We also show that, to find the center of a trapezoid graph, it is not necessary to find the eccentricity of all vertices. Based on our studied results, we design an optimal algorithm for finding the center, radius, and diameter of trapezoid graphs. Also, we prove theoretically that our proposed algorithm compiles within O ( n ) time. We also find an algorithmic solution to real problems (that involves finding a center location in a district to build a private hospital that minimizes the farthest distance from it to all areas of the district) with the help of the trapezoid graph model and BFS trees within O ( n ) time.