Using minimum spanning tree technique (MST), this exploratory research was done to optimize the interrelation and hierarchical network design of Indonesian’s airports. This research also identifies the position of the Indonesian’s airports regionally based on the ASEAN Open Sky Policy 2015. The secondary data containing distance between airports (both in Indonesia and in ASEAN), flight frequency, and correlation of Gross Domestic Regional Product (GDRP) for each region in Indonesia are used as inputs to form MST networks. The result analysis is done by comparing the MST networks with the existing network in Indonesia. This research found that the existing airport network in Indonesia does not depict the optimal network connecting all airports with the shortest distance and maximizing the correlation of regional economic potential in the country. This research then suggests the optimal networks and identifies the airports and regions as hubs and spokes formed by the networks. Lastly, this research indicates that the Indonesian airports have no strategic position in the ASEAN Open Sky network, but they have an opportunity to get strategic positions if 33 airports in 33 regions in Indonesia are included in the network.