{"ID":2842711,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.09132","arxiv_id":"2511.09132","title":"A Spanning-Tree-Based Algorithm for Planar Graph Dismantling","abstract":"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.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2511.09132","url_pdf":"https://arxiv.org/pdf/2511.09132v1","authors":"[\"Fangchen You\"]","published":"2025-11-12T09:16:10Z","proceeding":"cs.SI","tasks":"[\"cs.SI\",\"cs.DS\"]","methods":"[]","has_code":false}