Search

This paper presents new results on nonseparating cocircuits in binary matroids. The first result states that for any 3-connected binary matroid M and for any basis B of M, there exists at least two nonseparating B-fundamental cocircuits in M. The second result provides a weakened version of this result for nonseparable binary matroids that are also simple and cosimple. The final states that if M is a nonseparable binary matroid, D is a nonseparating cocircuit of M, and e is an element of D, then M is graphic if and only if M/e is graphic and has a realization H in which D \{ e\} is a subset of the star of some node of H. All of these results are shown to lead to efficient algorithms. [ABSTRACT FROM AUTHOR]

It is shown that a binary matroid is graphic if and only if it does not contain a cyclically ordered circuit and two cocircuits that interact in a particular way. This result generalizes a theorem of Doffšen and Petrić for planar graphs. [ABSTRACT FROM AUTHOR]

It is well known that every cycle of a graph must intersect every cut in an even number of edges. For planar graphs, Ford and Fulkerson proved that, for any edge e, there exists a cycle containing e that intersects every minimal cut containing e in exactly two edges. The main result of this paper generalizes this result to any nonplanar graph G provided G does not have a K 3,3 minor containing the given edge e. Ford and Fulkerson used their result to provide an efficient algorithm for solving the maximum-flow problem on planar graphs. As a corollary to the main result of this paper, it is shown that the Ford-Fulkerson algorithm naturally extends to this more general class of graphs. [ABSTRACT FROM AUTHOR]

Focuses on a study which described an efficient algorithm for graph realization. Definition of terms and notations; Outline of L ö fgren's procedure; Details on developed subroutines.