Graph Orientations and Their Algorithmic Applications

BSF grant proposal no. 2018364 GraphOrientationsandTheirAlgorithmic Applications Tsvi Kopelowitz Ely Porat Clifford Stein Bar-Ilan University Bar-Ilan University Columbia University Graphs and networks model many important applications that are vital for the efficient functioning of modern society, and address fundamental problems in a variety of fields in science, engineering, economics and beyond. A graph is a collection of objects (nodes) and descriptions of relationships between the objects (edges). For example, the nodes may represent people and the edges may connect two people who like each other. As many important problems involve large graphs, it is essential that we can compute efficiently on graphs. One important primitive is known as orientation, which is assigning each edge a direction, i.e., an edge points towards one node and away from another.

Typically the goal is to orient edges so that nodes has few edges pointing outwards.

Graph orientations have been successfully applied in a wide spectrum of computational appli- cations. However, currently there is no comprehensive theory of orientations, nor is there a well developed methodology for applying them in the design and analysis of algorithms.

The main goal of this project is to provide an advanced algorithmic theory for graph orientations in graphs that undergo changes. Concretely, we propose to undertake a thorough treatment of ori- entations and their algorithmic applications by pursuing the following activities: (1) designing new fundamental orientation algorithms and data structures, particularly for simple structures, (2) expand- ing the ideas used in algorithms for orientations in simple structures to more complicated structures, and (3) applying and analyzing orientations as an algorithmic tool for important applications, leading to simpler and practical algorithms.