In many application fields (robotics, computer vision, sensor networks, etc.) we find inference problems in which the variables live on the edge of a graph that has a spatial embedding. Often the variables to be estimated are elements of Lie groups, and the available measurements are relative measurements corresponding to the edges of the graph. I will discuss the main variations of this problem across the fields, comment on differences and similarities, and explain the technical issues (nonconvexity, multiple minima, possible presence of outliers, etc.) that make this problem difficult. I will describe my contributions that enable finding the complete set of all local minima in some special cases, and current work that aims at finding efficient solutions with performance and robustness guarantees when globally optimal solutions are not obtainable.