This thesis presents a novel navigation framework established to enable the exploration of planetary subterranean areas with Unmanned Aerial Vehicles (UAVs). The key contributions of this thesis work form a robot-safe rapid navigation framework that utilizes a novel bifurcating frontier-based exploration approach. UAVs (limited to quadrotors in this work) have superior navigation capabilities compared to ground robots in terms of 3D navigation as well as fast and versatile Traversability. Utilizing this advantage, this thesis investigates exploration and path-planning problems and presents novel mission behavior-oriented exploration strategies that are evaluated through either simulation with true physics and atmospheric models of planetary bodies or real-world deployment in subterranean areas.  The work included in this thesis is focused on two main research directions. The first direction establishes a novel coaxial quadrotor design that can operate in the thin atmosphere of Mars and utilize the Mars Coaxial Quadrotor (MCQ) to develop an energy-efficient exploration algorithm that leads to autonomously map Martian underground lava channel through true atmospheric model-based simulations. While the second direction establishes a Rapid Exploration Framework (REF) for the real-world deployment for the exploration of GPS-denied underground environments with UAVs. The contributions in the two directions are merged to develop a field-hardened autonomous exploration pipeline for UAVs that focuses on maintaining the heading vector of the UAV towards the most unknown area ahead of the UAV. While also bifurcating the exploration problem in local and global exploration for rapid navigation towards the unknown areas in the field of view and quickly globally re-positioning to a partially explored area. For navigating to the exploration goal of the UAV, it utilizes an expendable grid-based risk-aware path planning framework (D$^{*}_{+}$) that explicitly models unknown areas as risk and plans paths in safe space and for local obstacle avoidance and control the framework utilizes Artificial Potential Fields (APF) and a nonlinear Model Predictive Control based reference tracking scheme.Based on the learnings from field experiments and limitations of state-of-the-art grid-based planning methods on large-scale maps, the final contribution of the thesis establishes a Grid + Graph oriented Traversability-aware exploration and planning framework. The graph-based exploration method proposed in this thesis utilizes geometric shapes to define local traversable paths for the UAV to navigate to the local exploration goal. While utilizing a traversable graph that incrementally plans paths to the edge vertex of sub-maps in the direction of the global re-position goal. The strategy is evaluated extensively in simulations in subterranean urban, tunnel, and cave environments while it is also tested in real-world deployment at test mines of EPIROC and LKAB in Sweden.