Optimized algorithm to find all symmetry-distinct maps of a graph: application to topology-driven molecular design

摘要

We describe an optimized algorithm for finding all symmetry-distinct maps of a given graph. It contains significant improvements on the computing time by representing the maps as linear codes. In this way, the time consuming step of removing equivalent maps can be solved more efficiently by searching for a “minimal code”. As an example we apply the algorithm to the 32-vertex Dyck-graph for which more than 4 billion cases should be investigated. One of its most symmetrical maps forms an interesting blueprint for a hypothetical negatively curved carbon allotrope of genus 3.