When the edge between two nodes is not measured, is there any hint to know the edge property, and will the inferred edge property be useful? To answer these questions, this paper uniformly defines the properties of unmeasurable edges in generic graphs. For an unmeasurable edge$(i,j)$, it is called rangeable if its length is unique in any realization of the graph, rigid if the number of its possible lengths is finite, and flexible if it has infinite possible lengths. The rangeable edge can provide deterministic hidden knowledge as if the edge is measured. A condition for an unmeasured edge being rangeable in 2D space is firstly proposed, based on which a centralized identification algorithm (DRE) is designed. However, the centralized rangeable edge identification has the overhead of global information collection. Therefore distributed condition and algorithm to identify rangeable edges are further investigated. We prove that an unmeasurable edge$(i,j)$is rangeable if there are at least two Disjoint Minimally Rigid Branches (DMRBs) between$i$and$j$. The unmeasurable edge$(i,j)$is rigid and flexible when the number of DMRB is one and zero, respectively. A distributed Branching and Blacklisting (BB) algorithm is proposed to find DMRBs, so that rangeable edges are identified distributively. Then, the applications of rangeable, rigid, and flexible edges are discussed. Experimental evaluations show that the centralized and distributed algorithms can identify a rich set of unmeasurable but rangeable edges in distance graphs, even more than the number of directly measured edges. Moreover, BB has a similar identification performance as the centralized DRE algorithm and outperforms existing distributed unmeasurable edge inference algorithms significantly.

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 .