The focus of this paper is on base functionalities required for UAV-based rapid deployment of an ad hoc communication infrastructure in the initial phases of rescue operations. The general idea is to use heterogeneous teams of UAVs to deploy communication kits that include routers. These kits will then be used in the generation of ad hoc Wireless Mesh Networks. A fundamental problem, known as the Router Node Placement problem (RNP) is to determine how one can optimally place such routers. An extended version of the RNP problem is specified that takes into account additional constraints that arise in actual field usage. This extended problem is solved with a new algorithm, RRT-WMN, based on a novel use of the Rapidly Exploring Random Trees (RRT) algorithm used in motion planning. A comparative empirical evaluation between RRT-WMN and existing techniques, CMA-ES and PSO, shows that the RRT-WMN algorithm has far better performance both in time and coverage as the extended RNP problem scales to realistic scenarios.