In this thesis, motivated by the problem of how to unambiguously associate a topological radio graph generated by crowd-sourced RSS measurements to an isomorphic Euclidean graph representing the physical space, we study automorphism in graphs and address the question of how much information is required to resolve detected automorphisms.

We focus on weighted graphs but our results apply to unweighted graphs as well. We introduce the concepts of Minimum Symmetric Structure (MSS) and Co-rooted Congruent Structures (COCSs) which provide the geometric interpretation of automorphisms, and describe our algorithm for detecting these structures. Then, we explain how ambiguities caused by these structures can be resolved by vertex, edge or position marking. We formulate the optimal marke...[ Read more ]

In this thesis, motivated by the problem of how to unambiguously associate a topological radio graph generated by crowd-sourced RSS measurements to an isomorphic Euclidean graph representing the physical space, we study automorphism in graphs and address the question of how much information is required to resolve detected automorphisms.

We focus on weighted graphs but our results apply to unweighted graphs as well. We introduce the concepts of Minimum Symmetric Structure (MSS) and Co-rooted Congruent Structures (COCSs) which provide the geometric interpretation of automorphisms, and describe our algorithm for detecting these structures. Then, we explain how ambiguities caused by these structures can be resolved by vertex, edge or position marking. We formulate the optimal marker selector to a set cover problem, then relax this set cover problem to a linear programming. With the markers reported by our algorithm, we can then uniquely label the vertices in a graph. The purpose of automorphism resolution is two-fold. First, it distinguishes the two identical halves of a symmetric object and identical structures. Second, it provides information for unambiguous data representation. Automorphism resolution can be applied to many areas, such as indoor localization and navigation, chemistry, biology, network design and management, etc.

In many Simultaneous Localization And Mapping (SLAM) survey-free systems, including the Adaptive indoor Wi-Fi Positioning System (AWPS) we proposed earlier, there is a need to associate unlabeled measurements to a floor plan. To achieve the association, we first develop a floor plan analysis system to extract key geographic information from a paper floor plan and create a weighted graph for the indoor environment. Then, apply automorphism resolution to the graphs from hypothetical floor plans as well as floor plans used in AWPS and other existing systems, we will demonstrate that often very few location labels are needed in a SLAM system.