Abstract
We prove that a connected cographic matroid of a graph G is the bias matroid of a signed graph Σ iff G imbeds in the projective plane. In the case that G is nonplanar, we also show that Σ must be the projective-planar dual signed graph of an actual imbedding of G in the projective plane. As a corollary we get that, if G1, . . . , G29 denote the 29 nonseparable forbidden minors for projective-planar graphs, then the cographic matroids of G1, . . . , G29 are among the forbidden minors for the class of bias matroids of signed graphs. We will obtain other structural results about bias matroids of signed graphs along the way.
| Original language | English |
|---|---|
| Pages (from-to) | 207-217 |
| Number of pages | 11 |
| Journal | Discrete Mathematics |
| Volume | 301 |
| Issue number | 2-3 |
| DOIs | |
| State | Published - Oct 6 2005 |
ASJC Scopus Subject Areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
Keywords
- Cographic
- Matroid
- Projective plane
- Signed graph
Disciplines
- Applied Mathematics
- Applied Statistics
- Mathematics