zbMATH — the first resource for mathematics

Characterizing graphic matroids by a system of linear equations. (English) Zbl 1408.05029
Summary: Given a rank-\(r\) binary matroid we construct a system of \(O(r^3)\) linear equations in \(O(r^2)\) variables that has a solution over GF(2) if and only if the matroid is graphic.

05B35 Combinatorial aspects of matroids and geometric lattices
52B40 Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.)
Full Text: DOI
[1] Bixby, R. E.; Cunningham, W. H., Converting linear programs to network problems, Math. Oper. Res., 5, 321-357, (1980) · Zbl 0442.90095
[2] Bixby, R. E.; Wagner, D. K., An almost linear-time algorithm for graph realization, Math. Oper. Res., 13, 99-123, (1988) · Zbl 0654.05023
[3] de Fraysseix, H., A characterization of circle graphs, European J. Combin., 5, 223-238, (1984) · Zbl 0551.05056
[4] Fujishige, S., An efficient PQ-graph algorithm for solving the graph-realization problem, J. Comput. System Sci., 21, 63-86, (1980) · Zbl 0438.68028
[5] Mighton, J., A new characterization of graphic matroids, J. Combin. Theory Ser. B, 98, 1253-1258, (2008) · Zbl 1170.05020
[6] Naji, W., Reconnaissance des graphes de cordes, Discrete Math., 54, 329-337, (1985) · Zbl 0567.05033
[7] Tutte, W. T., An algorithm for determining whether a given binary matroid is graphic, Proc. Amer. Math. Soc., 11, 905-917, (1960) · Zbl 0097.38905
[8] Tutte, W. T., Lectures on matroids, J. Res. Natl. Bur. Stand. Sect. B, 69, 1-47, (1965) · Zbl 0151.33801
[9] Wagner, D. K., On mightonʼs characterization of graphic matroids, J. Combin. Theory Ser. B, 100, 493-496, (2010) · Zbl 1203.05030
[10] Whitney, H., Non-separable and planar graphs, Trans. Amer. Math. Soc., 34, 339-362, (1932) · JFM 58.0608.01
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.