Quasi-Isometric Graph-Simplifications
share
We propose a general framework based on quasi-isometries to study graph simplifications. Quasi-isometries are mappings on metric spaces that preserve the distance functions within an additive and a multiplicative constant. We use them to measure the distance distortion between the original graph and the simplified graph. We also introduce a novel concept called the centre-shift, which quantifies how much a graph simplification affects the location of the graph centre. Given a quasi-isometry, we establish a weak upper bound on the centre-shift. We present methods to construct so-called partition-graphs, which are quasi-isometric graph simplifications. Furthermore, in terms of the centre-shift, we show that partition-graphs constructed in a certain way preserve the centres of trees. Finally, we also show that by storing extra numerical information, partition-graphs preserve the median of trees.
READ FULL TEXT