A Spanning-Tree-Based Algorithm for Planar Graph Dismantling
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909899351392256 |
|---|---|
| author | You, Fangchen |
| author_facet | You, Fangchen |
| contents | In spatially embedded networks such as transportation and power grids, understanding how edge removals affect connectivity is crucial for robustness analysis. This paper studies a planar graph dismantling problem under an edge-budget constraint. We propose a spanning-tree-skeleton dual-path framework that first samples multiple uniform spanning trees to capture network backbones and then adaptively selects between two complementary paths according to the budget. The small-budget path estimates a dismantlable subgraph fraction using a logarithmic density feature, while the large-budget path predicts the optimal partition count through a slope-based model. Experiments on random planar graphs demonstrate near-linear runtime scaling, consistent reductions in the largest connected component ratio, and clear budget-fragmentation trends. The method provides an interpretable and efficient approach for planar-network robustness analysis. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_09132 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Spanning-Tree-Based Algorithm for Planar Graph Dismantling You, Fangchen Social and Information Networks Data Structures and Algorithms In spatially embedded networks such as transportation and power grids, understanding how edge removals affect connectivity is crucial for robustness analysis. This paper studies a planar graph dismantling problem under an edge-budget constraint. We propose a spanning-tree-skeleton dual-path framework that first samples multiple uniform spanning trees to capture network backbones and then adaptively selects between two complementary paths according to the budget. The small-budget path estimates a dismantlable subgraph fraction using a logarithmic density feature, while the large-budget path predicts the optimal partition count through a slope-based model. Experiments on random planar graphs demonstrate near-linear runtime scaling, consistent reductions in the largest connected component ratio, and clear budget-fragmentation trends. The method provides an interpretable and efficient approach for planar-network robustness analysis. |
| title | A Spanning-Tree-Based Algorithm for Planar Graph Dismantling |
| topic | Social and Information Networks Data Structures and Algorithms |
| url | https://arxiv.org/abs/2511.09132 |