Oriented Diameter of Graphs

Consider the road network in a small town where all roads are narrow and open to two-way traffic. A committee constituted to find a solution to the rising number of road accidents recommended that traffic should be restricted to a single direction in every street of this town. The feasibility of this proposition clinches on this question. Is it possible to assign a single direction for traffic in each street of the town and still drive from any point in the town to another? Let us call any assignment of traffic directions to each street which ensures the above critical requirement of point-to-point connectivity as a feasible solution. If there are multiple feasible solutions then how does the town administration pick one solution from the available options? One possible consideration might be to pick a solution that minimises the maximum point-to-point driving distance. Hence the following number becomes critical to the public acceptance of this recommendation. What is the maximum point-to-point driving distance in the town when one chooses a feasible solution that minimises the same? In very large towns, the administration will also have to grapple with the computational question of finding an optimal or near-optimal feasible solution. One can narrate a similar story of converting a bidirectional computer network to a unidirectional one where point-to-point distances translate to end-to-end delays. These are all manifestations of a nice graph theoretic problem, which is being investigated in the project.