Veröffentlichung

Titel:

Oriented dilation of undirected graphs

AutorInnen:

Kevin Buchin
Antonia Kalb
Carolin Rehs
André Schulz

Kategorie:

Konferenzbandbeiträge

erschienen in:

40th European Workshop on Computational Geometry (EuroCG 2024), Ioannina, Greece 2024

Abstract:

Given an oriented graph $\overrightarrow{G}$ on a set of points P in the Euclidean plane, the oriented dilation of p, p′ ∈ P is the ratio of the length of the shortest cycle in $\overrightarrow{G}$ through p and p′ to the perimeter of the smallest triangle in P containing p and p′. The oriented dilation of $\overrightarrow{G}$ is maximum oriented dilation over all pair of points. We show that given an undirected graph G on P , it is NP-hard to decide whether the edges can be oriented in way that the oriented dilation of the resulting graph is below a given threshold. For the case that G is complete, it is known that there is always an orientation of the edges with oriented dilation at most 2. As a first step towards improving this bound, we show that for |P| = 4 there is always a tournament, i.e., an oriented complete graph, with oriented dilation at most 1.5. This holds not only in the Euclidean but more generally in the metric plane. In the latter the bound is tight.

$\stackrel{}{}$

Download:

EuroCG 2024