Space-Efficient Graph Coarsening with Applications to Succinct Planar Encodings
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929390255865856 |
|---|---|
| author | Hammer, Nina Kammer, Frank Meintrup, Johannes |
| author_facet | Hammer, Nina Kammer, Frank Meintrup, Johannes |
| contents | We present a novel space-efficient graph coarsening technique for $n$-vertex planar graphs $G$, called cloud partition, which partitions the vertices $V(G)$ into disjoint sets $C$ of size $O(\log n)$ such that each $C$ induces a connected subgraph of $G$. Using this partition $P$ we construct a so-called structure-maintaining minor $F$ of $G$ via specific contractions within the disjoint sets such that $F$ has $O(n/\log n)$ vertices. The combination of $(F, P)$ is referred to as a cloud decomposition.
For planar graphs we show that a cloud decomposition can be constructed in $O(n)$ time and using $O(n)$ bits. Given a cloud decomposition $(F, P)$ constructed for a planar graph $G$ we are able to find a balanced separator of $G$ in $O(n/\log n)$ time. Contrary to related publications, we do not make use of an embedding of the planar input graph. We generalize our cloud decomposition from planar graphs to $H$-minor-free graphs for any fixed graph $H$. This allows us to construct the succinct encoding scheme for $H$-minor-free graphs due to Blelloch and Farzan (CPM 2010) in $O(n)$ time and $O(n)$ bits improving both runtime and space by a factor of $Θ(\log n)$.
As an additional application of our cloud decomposition we show that, for $H$-minor-free graphs, a tree decomposition of width $O(n^{1/2 + ε})$ for any $ε> 0$ can be constructed in $O(n)$ bits and a time linear in the size of the tree decomposition. Finally, we implemented our cloud decomposition algorithm and experimentally verified its practical effectiveness on both randomly generated graphs and real-world graphs such as road networks. The obtained data shows that a simplified version of our algorithms suffices in a practical setting, as many of the theoretical worst-case scenarios are not present in the graphs we encountered. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2205_06128 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Space-Efficient Graph Coarsening with Applications to Succinct Planar Encodings Hammer, Nina Kammer, Frank Meintrup, Johannes Data Structures and Algorithms We present a novel space-efficient graph coarsening technique for $n$-vertex planar graphs $G$, called cloud partition, which partitions the vertices $V(G)$ into disjoint sets $C$ of size $O(\log n)$ such that each $C$ induces a connected subgraph of $G$. Using this partition $P$ we construct a so-called structure-maintaining minor $F$ of $G$ via specific contractions within the disjoint sets such that $F$ has $O(n/\log n)$ vertices. The combination of $(F, P)$ is referred to as a cloud decomposition. For planar graphs we show that a cloud decomposition can be constructed in $O(n)$ time and using $O(n)$ bits. Given a cloud decomposition $(F, P)$ constructed for a planar graph $G$ we are able to find a balanced separator of $G$ in $O(n/\log n)$ time. Contrary to related publications, we do not make use of an embedding of the planar input graph. We generalize our cloud decomposition from planar graphs to $H$-minor-free graphs for any fixed graph $H$. This allows us to construct the succinct encoding scheme for $H$-minor-free graphs due to Blelloch and Farzan (CPM 2010) in $O(n)$ time and $O(n)$ bits improving both runtime and space by a factor of $Θ(\log n)$. As an additional application of our cloud decomposition we show that, for $H$-minor-free graphs, a tree decomposition of width $O(n^{1/2 + ε})$ for any $ε> 0$ can be constructed in $O(n)$ bits and a time linear in the size of the tree decomposition. Finally, we implemented our cloud decomposition algorithm and experimentally verified its practical effectiveness on both randomly generated graphs and real-world graphs such as road networks. The obtained data shows that a simplified version of our algorithms suffices in a practical setting, as many of the theoretical worst-case scenarios are not present in the graphs we encountered. |
| title | Space-Efficient Graph Coarsening with Applications to Succinct Planar Encodings |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2205.06128 |