This method for computing a conjugated airport navigation graph, from an initial airport navigation graph, is implemented by a computer.This method involves acquiring the initial graph including a plurality of navigation arcs, each including two end nodes, having at least one authorized navigation direction and being identified by its two end nodes.This method further involves determining a conjugated node for each navigation arc and for each authorized navigation direction of the arc, each conjugated node corresponding to a single authorized direction and representing the arc of the initial graph associated with the authorized direction. The conjugated graph is computed by connecting the conjugated nodes as a function of the connections between the arcs of the initial graph and the authorized directions. Two conjugated nodes connect to one another corresponding to two successive arcs of the initial graph and to a same authorized direction.