In structure-from-motion (SfM), the viewing graph is a graph where vertices correspond to cameras and edges represent fundamental matrices encoding the epipolar geometry between image pairs. A fundamental question is whether a given viewing graph is solvable — that is, whether the camera matrices can be uniquely recovered (up to a projective ambiguity) from the given fundamental matrices. This paper advances the theoretical understanding of viewing graph solvability by exploiting cycle consistency. The authors complete the classification of all previously undecided minimal graphs up to 9 nodes, extend practical solvability testing up to minimal graphs with 90 nodes, and prove that finite solvability is not equivalent to solvability, resolving a long-standing open question in multi-view geometry.

Structure-from-motion aims to recover 3D scene structure and camera poses from a collection of 2D images. The viewing graph encodes which image pairs share epipolar relationships (fundamental matrices). Before attempting reconstruction, a natural question arises: is the viewing graph configuration solvable? An unsolvable graph means that even with perfect, noise-free fundamental matrices, the camera matrices cannot be uniquely determined. Understanding solvability is thus essential for designing robust SfM pipelines — it tells us whether a given set of pairwise relationships contains sufficient constraints to determine the global configuration. Prior work has classified solvability for small graphs but left many cases undecided and lacked efficient methods for larger graphs.

The study of viewing graph solvability originates from Trager et al., who formalized the problem using algebraic geometry and classified graphs up to 4 nodes. Duff et al. extended this work using numerical algebraic geometry techniques to handle larger cases, but left several graphs undecided due to computational limitations. In parallel, cycle consistency has been recognized as a fundamental property of multi-view geometry: a set of fundamental matrices is globally consistent if and only if certain conditions hold on every cycle in the viewing graph. This paper is the first to systematically exploit cycle consistency as a tool for solvability analysis, enabling both theoretical classification and practical scalability.

A viewing graph G = (V, E) consists of vertices V representing n cameras with 3x4 projection matrices P_i, and edges E representing fundamental matrices F_ij that encode the epipolar constraint between camera pairs. A viewing graph is solvable if, for generic camera matrices, the corresponding fundamental matrices uniquely determine the cameras up to a projective transformation. It is finitely solvable if the cameras can be recovered up to a finite number of solutions. A minimal graph is one where removing any edge makes the graph unsolvable. The paper focuses on classifying which minimal graph topologies are solvable.

The key methodological innovation is using cycle consistency constraints for solvability analysis. For any cycle in the viewing graph (a closed sequence of edges), the composition of the fundamental matrices along the cycle must satisfy certain algebraic conditions. Specifically, the product of epipolar transfers around a cycle must be consistent — it must correspond to a valid projective transformation. The authors show that checking cycle consistency conditions across all independent cycles in the graph provides a powerful criterion for solvability. When all cycle consistency conditions are satisfied, the fundamental matrices are globally compatible with a set of camera matrices. When they fail, the graph is provably unsolvable. This approach reduces the solvability problem to checking conditions on cycles rather than solving the full system of polynomial equations.

Using the cycle consistency framework, the authors achieve three key results. First, they complete the classification of all minimal graphs up to 9 nodes — resolving all previously undecided cases. Second, they extend practical solvability testing to minimal graphs with up to 90 nodes, a dramatic improvement over prior methods limited to about 10 nodes. Third, and most significantly, they prove that finite solvability is strictly weaker than solvability — there exist graphs that are finitely solvable but not solvable. This means that having a finite number of solutions does not guarantee uniqueness, refuting a conjecture that the two notions might be equivalent. This result has implications for SfM algorithms that rely on counting solution numbers to assess reconstruction quality.

The authors validate their theoretical results with experiments on both synthetic and real data. On synthetic data, they verify the correctness of their classification by generating random camera configurations and checking whether reconstruction succeeds or fails as predicted by the theory. On real datasets from standard SfM benchmarks, they demonstrate that unsolvable subgraph configurations do appear in practice — these are not mere theoretical curiosities. Specifically, they identify viewing graph substructures that are provably unsolvable, confirming that awareness of graph solvability is practically relevant for robust SfM pipeline design. The experiments also demonstrate that the cycle-consistency-based testing is computationally efficient enough for real-world graph sizes.

This paper advances the theory of viewing graph solvability through three contributions: completing the classification of minimal graphs up to 9 nodes, scaling practical testing to 90-node graphs, and proving that finite solvability is not equivalent to solvability. The cycle consistency framework provides an efficient and principled tool for analyzing graph solvability. The practical experiments confirm that unsolvable configurations occur in real SfM scenarios, motivating the integration of solvability checks into reconstruction pipelines. Future work includes extending the analysis to non-minimal graphs and developing real-time solvability verification for use in incremental SfM systems.