Abstract:
This thesis studies some theoretical aspects of graph simplifications. Graph simplifications
are methods to transform a graph into a smaller representation such that computation
on the simplified representation becomes more efficient while remaining reasonably
accurate. The distance query is a common computation task on graphs, and we introduce the concept
of quasi-isometries as a measure of the distance distortions of graph simplifications.
We also introduce a generic graph simplification method called partition-graphs. This
method constructs a new graph based on a partition of the original vertices into
subsets that induce connected subgraphs. We establish that a partition-graph is quasi-isometric to
the original graph, with the quasi-isometry’s parameters depending on the diameters of the
subsets.
In addition to studying quasi-isometries and distance distortions, we investigate the
preservation of two centrality concepts: the centre and the median. Although we have found
partition-graphs of trees that do not preserve the centres and medians, we show
specific method of constructing partition-graphs of a tree that preserves the centre or the median.
Finally, we focus on the set of all possible partition-graphs of a path, which are
called partition-paths and can be viewed as integer compositions with restricted part-sizes. Under
three specific settings, we use combinatorial techniques to derive a recurrence to count the total
number of balanced partition-paths, and establish regular-language characterisations of the
possible outcomes of two probabilistic path-partitioning algorithms.