Reduction of CO2 emissions from industrial facilities is of utmost importance for sustainable development. Novel process systems with the capability to remove CO2 will be useful for carbon management in the future. It is well-known that major determinants of performance in process systems are established during the design stage. Thus, it is important to employ a systematic tool for process synthesis. This work approaches the design of polygeneration plants with negative emission technologies (NETs) by means of the graph-theoretic approach known as the P-graph framework. As a case study, a polygeneration plant is synthesized for multiperiod operations. Optimal and alternative near-optimal designs in terms of profit are identified, and the influence of network structure on CO2 emissions is assessed for five scenarios. The integration of NETs is considered during synthesis to further reduce carbon footprint. For the scenario without constraint on CO2 emissions, 200 structures with profit differences up to 1.5% compared to the optimal design were generated. The best structures and some alternative designs are evaluated and compared for each case. Alternative solutions prove to have additional practical features that can make them more desirable than the nominal optimum, thus demonstrating the benefits of the analysis of near-optimal solutions in process design.