B1-ORIENTABLE GRAPHS

The aim of this paper is to find a particular orientation U of an undirected graph G = (X, E), called B1 –orientation [1]. The directed graph G0 = (X,U) is such that: u, v, w Î X ,(u,v) ÎU and (w, v) ÎU implies that the edge [uw] ÎE. This class of B1 -orientable graphs includes triangulated graphs and arc-circular graphs, as mentioned in [2,3]. We propose here, an algorithm which gives a B1 -orientation of an undirected graph G = (X, E) if G is B1 -orientable or exits with output: G is not B1 -orientable. The complexity of this algorithm is in O(n.D2 ), where n = X and D is the maximum degree of G. We show too, by an algorithm, that the class of triangulated graphs is included in this new class of graphs [4,5].