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