Search

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]

Graph minors play an important role in graph theory. The focus of this paper is on immersion minors and their relationship to planarity. In general, planar graphs can have non-planar immersion minors. This paper shows that by placing a simple restriction on the immersion-minor operations, all immersion minors of a planar graph are planar. This then allows one to easily obtain a characterization of planar graphs using immersion minors. A dual form of this characterization, as well as an extension to binary matroids, are also considered. [ABSTRACT FROM AUTHOR]

It is shown that a binary matroid is graphic if and only if it does not contain four circuits that interact is a particular way. This result generalizes a theorem of Little and Sanjith for planar graphs. [ABSTRACT FROM AUTHOR]

A non-planar graph G is almost planar if, for every edge e of G , either G ∖ e or G / e is planar. The main result of this paper is that every almost-planar graph is delta–wye reducible to K 3 , 3 , and moreover, there exists a reduction sequence in which every graph is almost planar. Analogous results are shown to hold for other classes of graphs, and also for regular, almost-graphic matroids. [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]