  The formation trajectory planning using complete graphs to model
collaborative constraints becomes computationally intractable as the number of
drones increases due to the curse of dimensionality. To tackle this issue, this
paper presents a sparse graph construction method for formation planning to
realize better efficiency-performance trade-off. Firstly, a sparsification
mechanism for complete graphs is designed to ensure the global rigidity of
sparsified graphs, which is a necessary condition for uniquely corresponding to
a geometric shape. Secondly, a good sparse graph is constructed to preserve the
main structural feature of complete graphs sufficiently. Since the graph-based
formation constraint is described by Laplacian matrix, the sparse graph
construction problem is equivalent to submatrix selection, which has
combinatorial time complexity and needs a scoring metric. Via comparative
simulations, the Max-Trace matrix-revealing metric shows the promising
performance. The sparse graph is integrated into the formation planning.
Simulation results with 72 drones in complex environments demonstrate that when
preserving 30\% connection edges, our method has comparative formation error
and recovery performance w.r.t. complete graphs. Meanwhile, the planning
efficiency is improved by approximate an order of magnitude. Benchmark
comparisons and ablation studies are conducted to fully validate the merits of
our method.
