In this paper, we propose two different algorithms for Shannon Factor Graph (SFG) construction, which can be used for cut-less mapping, to improve the runtime, graph size and required memory size. The first SFG construction algorithm does not consider the nature of the nodes (constant one and zero, non-decomposed and shared nodes) while building the SFG, whereas the second algorithm finds out the nature of the nodes on-the-fly. We observed that the constant one and zero, Shared and non-decomposed nodes can be used at the time of SFG construction to minimize the runtime and graph size significantly and to make the graph semi-canonical. The theoretical analysis and experiments performed on the standard benchmark circuits show that, by finding the constant one and zero, shared and non-decomposed nodes on-the-fly reduces the graph size by a factor of 126 and the runtime by a factor of 5.5. © 2014 IEEE.