Zunächst werden die zu vergleichenden Schaltungen als Graphen dargestellt. Beispielsweise können die Bauelemente und Netze als Knoten und die Verbindungen durch Kanten dargestellt werden. Alle Verfahren zum LVS lassen sich dann auf die Isomorphieuntersuchung zweier Graphen zurückführen. Dabei handelt es sich um ein bekanntes Problem, das im allgemeinen Fall, in dem keine Namenskorrespondenzen zwischen den Graphen bekannt sind, zur Klasse der NP-vollständigen (NP: Nicht-deterministisch Polynomial) Probleme gehört. Bei einem NP-vollständiges Peoblem nimmt die Rechenzeitkomplexität mit wachsender Problemgröße drastisch zu; diese Klasse von Problemen liese sich nur mit Hilfe einer nicht-deterministischen Turing-Maschine effizient lösen. Da keine solche Maschine existiert, ist notwendig das Problem zu vereinfachen und geeignete Algorithmen zur Lösung zu finden.