Name
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 miners. |
Year | Venue | Field |
|---|---|---|
1997 | ARS COMBINATORIA | Matroid,Discrete mathematics,Combinatorics,Signed graph,Graph embedding,k-edge-connected graph,Matroid partitioning,Null graph,Graphic matroid,Factor-critical graph,Mathematics |
DocType | Volume | ISSN |
Journal | 45 | 0381-7032 |
Citations | PageRank | References |
2 | 0.53 | 0 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| T. Zaslavsky | 1 | 297 | 56.67 |