Listing All st-Orient at ions

摘要

In this paper we give a simple algorithm to generate all st-orientations of a given biconnected plane graph G with designated two vertices on the outer face of G. Our algorithm generates all st-orientations of G in O(n) time for each on average without duplications, where n is the number of vertices.