The cycle structure for directed graphs on surfaces.

In this paper, the cycle structures for directed graphs on surfaces are studied. If G is a strongly connected graph, C is a Π- contractible directed cycle of G, then both of Int( C,Π) and Ext( C,Π) are strongly connected graph; the dimension of cycles space of G is identified. If G is a strongly connected graph, then the structure of MCB in G is unique. Let G be a strongly connected graph, if G has been embedded in orientable surface S with f( G) ≥ 2 ( f( G) is the face-width of G), then any cycle base of G must contain at least 2 g noncontractible directed cycles; if G has been embedded in non-orientable surface N, then any cycle base of G must contain at least g noncontractible directed cycles. [ABSTRACT FROM AUTHOR]