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.

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 Došen and Petrić for planar graphs.

This paper presents a polynomial-time algorithm for the minimum-weight-cycle problem on graphs that decompose via 3-separations into well-structured graphs. The problem is NP-hard in general. Graphs that decompose via 3-separations into well-structured graphs include Halin, outer-facial, delta-wye, wye-delta, flat, and twirl-wheel graphs. For each of these classes of graphs, given the decomposition, the algorithm runs in linear time. © 1997 John Wiley & Sons, Inc. Networks 29: 151–160, 1997

A $\{ 0,1\} $-matrix M has the consecutive-retrieval property if there exists a tree M such that the vertices of T are indexed on the rows of M and the columns of M are the incidence vectors of the vertex sets of paths of . If such a T exists, then T is a realization for M. In this paper, an $O(r^2 c)$ algorithm is presented to determine whether a given standard, $r \times c$ matrix has the consecutive-retrieval property and, if so, to construct a realization.

Abstract The 2‐connected Steiner subgraph problem is that of finding a minimum‐weight 2‐connected subgraph that spans a subset of distinguished vertices. This paper presents linear‐time algorithms for solving the 2‐connected Steiner subgraph problem on two special classes of graphs, W4‐free graphs and Halin graphs. Although different in detail, the algorithms adopt a common strategy exploiting known decompositions. As a special case, the algorithms also solve the Traveling Salesman Problem on W4‐free graphs and Halin graphs. © 1993 by John Wiley & Sons, Inc.

Abstract Consider a graph having distinguished vertices s and t, and a nonnegative, real‐valued cost associated with each edge. This paper considers variations on the problem of finding k pairwise‐disjoint (s, t)‐cuts of minimum total cost. For k = 1, this problem is a version of the well‐known minimum‐cut problem from network‐flow theory and, thus, is solvable in polynomial time. The main result of this paper is that for arbitrary k, the problem can be formulated as a specially structured transshipment problem and, thus, is solvable in polynomial time.

Abstract Series‐parallel graphs, outerplanar graphs, and graphs whose polygon matroids are transversal have been characterized by forbidden subgraphs. Tutte introduced a graph decomposition for nonseparable graphs. The results of this paper relate the existence of the forbidden subgraphs to properties of the decomposition. Algorithmic implications are considered.