- Title
- Recognizing pinch-graphic matroids
- KIAS Author
- Heo, Cheolwon
- Journal
- MATHEMATICAL PROGRAMMING, 2024
- Abstract
- Even-cycle matroids are elementary lifts of graphic matroids. An even-cycle matroid is pinch-graphic if it has a signed-graph representation with a blocking pair. We present a polynomial algorithm to check if an internally 4-connected binary matroid is pinch-graphic. Combining this with a result in Guenin and Heo (Small separations in pinch-graphic matroids. Math Program (2023). https://doi.org/10.1007/s10107-023-01950-8) this allows us to check, in polynomial time, if an arbitrary binary matroid is pinch-graphic.