- Visualization of k-connected Components and Minimum Separating Sets of Fixed Points of Degree Peeling
- Project Year:
2018
- REU Student (s):
Daniel Nakhimovich | Cooper Union for the Advancement of Science and Art NY
- Student 1 Institution:
Cooper Union for the Advancement of Science and Art
- Project Mentor:
James Abello
- Project Mentor Area:
Computer Science
- Project Abstract:
Graphs are an excellent form for the visualization of data because they clearly show how individual data points are connected. However, for large sets of data, a direct visualization of a graph is indecipherable to the human eye. Separating sets and k-connected components are interesting structures in graphs that highlight critical data points and clusters of highly connected points respectively. We developed an algorithm that uses minimum separating sets to decompose a graph into a hierarchy of k-connected components. The complexity of the algorithm depends linearly on the number of k-connected components in the graph. For each k-connected component K=(V,E), however, the complexity of finding its minimum separating set is $O(nm\binom{n}{2})$ where n=|V| and m=|E|. By using different approximate procedures this complexity can be improved to O(nm) or at more cost to accuracy to O(n+m). Performing the separating set decomposition creates a tree-structured map of the decomposed graph that more easily shows the connectivity of the graph and consequently the data it represents.
