Network planning is facing new and critical challenges due to ad hoc deployment, unbalanced and drastically varying traffic demands, as well as limited backhaul and hardware resources in emerging small cell architectures. We discuss the application of graph theory to address the challenges. A clique-based software-defined online network management approach is proposed that captures traffic imbalance and fluctuation of small cells and optimally plans frequencies, infrastructures, and network structure at any instant. Its applications to three important small cell scenarios of cloud radio, point-to-point microwave backhaul, and interoperator spectrum sharing are demonstrated. Comparison studies show that in each of the scenarios, this new approach is able to significantly outperform conventional static offline network planning schemes in terms of throughput and satisfaction levels of small cells with regard to allocated bandwidths. Specifically, the throughput can be improved by 155 percent for the cloud radio scenario and 110.95 percent for the microwave backhaul scenario. The satisfaction level can be improved by 40 percent for interoperator spectrum sharing.