Viktor Fredslund-Hansen

activity

20202026

collaborators

5 papers

cs.DS2026

A Tight Bound for Facial Distance Patterns in Planar Graphs

Viktor Fredslund-Hansen, Shay Mozes, Oren Weimann

Let $G$ be an undirected unweighted planar graph and let $S = (s_{0}, \dots, s_{k - 1})$ be the vertices of a designated face, listed in cyclic order. Consider a vector that stores the dis…

cs.CG2022

Degree of Convexity and Expected Distances in Polygons

Mikkel Abrahamsen, Viktor Fredslund-Hansen

We present an algorithm for computing the so-called Beer-index of a polygon $P$ in $O (n^{2})$ time, where $n$ is the number of corners. The polygon $P$ may have holes. The Beer-index…

cs.DS2021

Near-Optimal Distance Oracles for Vertex-Labeled Planar Graphs

Jacob Evald, Viktor Fredslund-Hansen, Christian Wulff-Nilsen

Given an undirected $n$ -vertex planar graph $G = (V, E, ω)$ with non-negative edge weight function $ω : E \to R$ and given an assigned label to each vertex, a vertex-label…

cs.DS2020

Decremental APSP in Directed Graphs Versus an Adaptive Adversary

Jacob Evald, Viktor Fredslund-Hansen, Maximilian Probst Gutenberg +1

Given a directed graph $G = (V, E)$ , undergoing an online sequence of edge deletions with $m$ edges in the initial version of $G$ and $n = ∣ V ∣$ , we consider the problem of maintaini…

cs.DS2020

Truly Subquadratic Exact Distance Oracles with Constant Query Time for Planar Graphs

Viktor Fredslund-Hansen, Shay Mozes, Christian Wulff-Nilsen

Given an undirected, unweighted planar graph $G$ with $n$ vertices, we present a truly subquadratic size distance oracle for reporting exact shortest-path distances between any pai…