Oriented spanners

Abstract

Geometric graphs naturally model numerous real-world infrastructures such as transportation systems, power grids and communication networks. Since fast connectivity is essential in these settings, geometric spanners are sparse graphs that approximately preserve pairwise distances.

Although spanners have been studied for decades, directed versions have only been considered more recently. In many applications, however, directionality is not merely optional. Physical constraints, limited resources, or safety regulations often require strictly unidirectional edges.

This motivates our study of oriented graphs as geometric spanners. In particular, we address the following problems:

- Oriented dilation: Given an oriented graph, we investigate how to compute or approximate its oriented dilation.

- Graph orientation: Given an undirected graph, we study algorithms to orient it.

- Spanner construction: Given a point set, we explore the construction of oriented spanners that satisfy additional properties such as sparseness or planarity.

For each problem, we analyze its computational complexity and provide algorithmic solutions.