4 papers
A Tight Bound for Facial Distance Patterns in Planar Graphs
Viktor Fredslund-Hansen, Shay Mozes, Oren Weimann
Let be an undirected unweighted planar graph and let be the vertices of a designated face, listed in cyclic order. Consider a vector that stores the dis…
Distances in Planar Graphs are Almost for Free!
Shay Mozes, Daniel Prigan
We prove that, up to subpolynomial or polylogarithmic factors, there is no tradeoff between preprocessing time, query time, and size of exact distance oracles for planar graphs. Na…
Ãptimal Fault-Tolerant Labeling for Reachability and Approximate Distances in Directed Planar Graphs
Itai Boneh, Shiri Chechik, Shay Golan +2
We present a labeling scheme that assigns labels of size to the vertices of a directed weighted planar graph , such that for any fixed from the lab…
Faster Construction of a Planar Distance Oracle with Ã(1) Query Time
Itai Boneh, Shay Golan, Shay Mozes +2
We show how to preprocess a weighted undirected -vertex planar graph in time, such that the distance between any pair of vertices can then be reported in $\t…