Air travel in recent years has been plagued by record delays, with over $8 billion in direct operating costs being attributed to 100 million flight delay minutes in 2007. Major contributing factors to delay include weather, congestion, and aging infrastructure; the Next Generation Air Transportation System (NextGen) aims to alleviate these delays through an upgrade of the air traffic control system. Changes to large-scale networked systems such as air traffic control are complicated by the need for coordinated solutions over disparate temporal and spatial scales. Individual air traffic controllers must ensure aircraft maintain safe separation locally with a time horizon of seconds to minutes, whereas regional plans are formulated to efficiently route flows of aircraft around weather and congestion on the order of every hour. More efficient control algorithms that provide a coordinated solution are required to safely handle a larger number of aircraft in a fixed amount of airspace. Improved estimation algorithms are also needed to provide accurate aircraft state information and situational awareness for human controllers. A hierarchical framework is developed to simultaneously solve the sometimes conflicting goals of regional efficiency and local safety. Careful attention is given in defining the interactions between the layers of this hierarchy. In this way, solutions to individual air traffic problems can be targeted and implemented as needed. First, the regional traffic flow management problem is posed as an optimization problem and shown to be NP-Hard. Approximation methods based on aggregate flow models are developed to enable real-time implementation of algorithms that reduce the impact of congestion and adverse weather. Second, the local trajectory design problem is solved using a novel slot-based sector model. This model is used to analyze sector capacity under varying traffic patterns, providing a more comprehensive understanding of how increased automation in NextGen will affect the overall performance of air traffic control. The dissertation also provides solutions to several key estimation problems that support corresponding control tasks. Throughout the development of these estimation algorithms, aircraft motion is modeled using hybrid systems, which encapsulate both the discrete flight mode of an aircraft and the evolution of continuous states such as position and velocity. The target-tracking problem is posed as one of hybrid state estimation, and two new algorithms are developed to exploit structure specific to aircraft motion, especially near airports. First, discrete mode evolution is modeled using state-dependent transitions, in which the likelihood of changing flight modes is dependent on aircraft state. Second, an estimator is designed for systems with limited mode changes, including arrival aircraft. Improved target tracking facilitates increased safety in collision avoidance and trajectory design problems. A multiple-target tracking and identity management algorithm is developed to improve situational awareness for controllers about multiple maneuvering targets in a congested region. Finally, tracking algorithms are extended to predict aircraft landing times; estimated time of arrival prediction is one example of important decision support information for air traffic control.