Printed circuit boards isomorphism: An experimental study

• Published in: Computers & industrial engineering 2020-10, Vol.148, p.106715, Article 106715
• Main Authors: Abiad, Aida, Grigoriev, Alexander, Niemzok, Stefanie
• Format: Article
• Language: English
• Subjects: Graph invariant; Graph isomorphism; Heuristic; Information retrieval; Preprocessing; Printed circuit board search engine
• ISSN: 0360-8352; 1879-0550
• DOI: 10.1016/j.cie.2020.106715

We evaluate the discrimination power of different graph invariants in order to identify an appropriate measurement of similarity among printed circuit boards. We show that computationally expensive algorithmic evaluation of circuit boards equivalence based on the topology of the circuit boards is unnecessary in practice. Instead, the information about the circuit boards can be stored in terms of graph invariants, namely, number sequences characterizing the boards, which requires much less memory and enables quicker recognition of board equivalence. This straightforwardly leads to fast practical implementations of the search engines for the printed circuit boards. Our approach is multidisciplinary, as the tools were drawn from two fields; the industrial electronic engineering field, and the theoretic fields of graph theory and algorithms. A real case study on a search engine for printed circuit boards is conducted to illustrate the proposed approach. Finding an easily computable and complete set of graph invariants remains a challenging mathematical question. •Physical circuit boards are modeled as graphs.•Graph invariants show high discrimination power on distinguishing circuit boards.•Integration of physical and relational knowledge of circuit boards in a search engine.