GPART: Partitioning Maximal Redundant Rigid and Maximal Global Rigid Components in Generic Distance Graphs

Proceedings of ICRA 2024

Yu Zhang, Qinhan Wei, Yongcai Wang,^*, Deying Li

School of Information, Renmin University of China, Beijing, 100872

Overview

Partitioning the Maximal Redundant Rigid Components (MRRC) and Maximal Global Rigid Components (MGRC) in generic 2D graphs are critical problem for network structure analysis, network localizability detection, and localization algorithm design. This article presents efficient algorithms to partition MRRCs and MGRCs and develops an open-sourced toolbox, GPART, for these algorithms to be conveniently used by the society. We firstly propose conditions and an efficient algorithm to merge the over-constrained regions to form the maximal redundant rigid components (MRRC). The detected MRRCs are proved to be maximal and all the MRRCs are guaranteed to be detected. The time to merge the over-constrained regions is linear to the number of nodes in the over-constrained components. To detect MGRCs, the critical problem is to decompose 3-connected components in each MRRC. We exploit SPQR-tree based method and design a local optimization algorithm, called MGRC_acce to prune the unnecessary decomposition operations so that the SPQR-tree functions can be called much less number of times. We prove the MGRCs can be detected inside MRRCs using at most O(mn) time. Then a GPART toolbox is developed and extensively tested in graphs of different densities. We show the proposed MRRC and MGRC detection algorithms are valid and MGRC_acce greatly outperforms the direct SPQR-tree based decomposition algorithm. GPART is outsourced at https://github.com/inlab-group/gpart.

Bibtex

xxxxxxxxxx
18
1
@article{10.1145/3594668,
2
author = {Zhang, Yu and Wei, Qinhan and Wang, Yongcai and Ping, Haodi and Li, Deying},
3
title = {GPART: Partitioning Maximal Redundant Rigid and Maximal Global Rigid Components in Generic Distance Graphs},
4
year = {2023},
5
issue_date = {November 2023},
6
publisher = {Association for Computing Machinery},
7
address = {New York, NY, USA},
8
volume = {19},
9
number = {4},
10
issn = {1550-4859},
11
url = {https://doi.org/10.1145/3594668},
12
doi = {10.1145/3594668},
13
journal = {ACM Trans. Sen. Netw.},
14
month = {jun},
15
articleno = {86},
16
numpages = {26},
17
keywords = {generic graph, graph algorithm, component partition, Graph rigidity}
18
}

Acknowledgment

This work was supported in part by the National Natural Science Foundation of China Grant No. 61972404, 12071478, Public Computing Cloud, Renmin University of China.