Skip to main navigation Skip to search Skip to main content

Is there a matroid theory of signed graph embedding?

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

A graph with signed edges is orientation embedded in a surface when it is topologically embedded and a polygon preserves or reverses orientation depending on whether its sign product is positive or negative. We study orientation- embedding analogs of three facts about unsigned graph embedding: planarity is equivalent to having cographic polygon matroid, the polygon matroid of a graph determines the surfaces in which it embeds, and contraction preserves embeddability of a graph in a surface. We treat three matroids of a signed graph. Our main results: For a signed graph which is orientation embeddable in the projective plane, the bias and lift matroids (which coincide) are cographic. Neither the bias nor lift nor complete lift matroid determines the surfaces in which a signed graph orientation embeds. Of the two associated contractions of signed edges, the bias contraction does not preserve orientation embeddability but the lift contraction does. Thus the signed graphs which orientation embed in a particular surface are characterizable by forbidden lift minors.

Original languageEnglish
Pages (from-to)129-141
Number of pages13
JournalArs Combinatoria
Volume45
StatePublished - Apr 1997

Fingerprint

Dive into the research topics of 'Is there a matroid theory of signed graph embedding?'. Together they form a unique fingerprint.

Cite this