arXiv:2611.13574v1 Announce Type: new Abstract: This paper studies the joint air corridor and base station (BS) coverage planning problem for high-density low-altitude aerial networks supported by terrestrial cellular infrastructures. In the considered system, unmanned aerial vehicles (UAVs) operate within a structured air corridor planned over a grid-based airspace, and each BS serves selected corridor grid cells by sharing its communication resources among all UAVs therein. Each BS's traffic load depends on both the number of covered corridor cells and the UAV density, thereby affecting the communication rate available to each UAV. We exploit the channel knowledge map (CKM) to characterize the channel gains between BSs and candidate airspace cells and evaluate desired signals and inter-cell interference for environment-aware offline planning. Based on CKM, we jointly optimize the corridor layout and BS coverage to minimize a weighted objective balancing corridor length and the supportable average UAV density along the entire corridor, subject to minimum communication rate requirements for all UAVs along the air corridor. The joint design is formulated as a mixed-integer linear program (MILP), which can be optimally solved using off-the-shelf solvers. For large maps, we develop a scalable suboptimal algorithm based on Lagrangian relaxation and A* search. Specifically, we incorporate BS resource constraints into A* corridor search via Lagrangian relaxation, and then jointly optimize BS coverage and UAV density along the generated corridors under the original rate constraints. Numerical results demonstrate the benefits of the proposed joint design in supporting high-density UAV operations and show that the proposed algorithm obtains high-quality solutions with substantially reduced computation time.