Unrestricted and complete Breadth-First Search of trapezoid graphs in O(n) time

We present an O(n) Breadth-First Search algorithm for trapezoid graphs, which takes as input a trapezoid model and any priority order on the vertices. Our algorithm is the first able to produce any BFS-tree, and not only one specific to the model given as input, within this complexity. Moreover, it produces all the shortest paths from the root of the BFS-tree to the other vertices of the graph.