subset of the braid arrangement, whose hyperplanes are the diagonals . Namely, if the vertices of are we include the hyperplane whenever is an edge of . Matroid connectivity A matroid is said to be connected if it is not the direct sum of two smaller matroids; that is, it is connected if and only if there do not exist two disjoint subsets of elements such that the rank function of the matroid equals the sum of the ranks in these separate subsets. Graphic matroids are connected if and only if the underlying graph is both connected and 2-vertex-connected. Minors and duality A matroid is graphic if and only if its minors do not include any of five forbidden minors: the uniform matroid , the Fano plane or its dual, or the duals of and defined from the complete graph and the complete bipartite graph . The first three of these are the forbidden minors for the regular matroids, and the duals of and are regular but not graphic. If a matroid is graphic, its dual (a "co-graphic matroid") cannot contain the duals of these five forbidden minors. Thus, the dual must also be regular, and cannot contain as minors the two graphic matroids and . Because of this characterization and Wagner's theorem characterizing the planar graphs as the graphs with no or graph minor, it follows that a graphic matroid is co-graphic if and only if is planar; this is Whitney's planarity criterion. If is planar, the dual of is the graphic matroid of the dual graph of . While may have multiple dual graphs, their graphic matroids are all isomorphic. Algorithms A minimum weight basis of a graphic matroid is a minimum spanning tree (or minimum spanning forest, if the underlying graph is disconnected). Algorithms for computing minimum spanning trees have been intensively studied; it is known how to solve the problem in linear randomized expected time in a comparison model of computation, or in linear time in a model of computation in which the edge weights are small integers and bitwise operations are allowed on their binary representations. The fastest known time bound that has been proven for a deterministic algorithm is slightly superlinear. Several authors have investigated algorithms for testing whether a given matroid is graphic. For instance, an algorithm of solves this problem when the input is known to be a binary matroid. solves this