Graph theory based methods are powerful means for representing structural systems so that their geometry and topology can be understood clearly. The combination of graph theory based methods and some metaheuristics can offer effective solutions for complex engineering optimization problems. This paper presents a Charged System Search (CSS) algorithm for the free shape optimizations of thin-walled steel sections, represented by some popular graph theory based methods. The objective is to find shapes of minimum mass and/or maximum strength for thin-walled steel sections that satisfy design constraints, which results in a general formulation for a bi-objective combinatorial optimization problem. A numerical example involving the shape optimization of thin-walled open and closed steel sections is presented to demonstrate the robustness of the method.