Premium
Orientation embedding of signed graphs
Author(s) -
Zaslavsky Thomas
Publication year - 1992
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190160503
Subject(s) - combinatorics , mathematics , embedding , vertex (graph theory) , orientation (vector space) , graph embedding , graph , signed graph , sign (mathematics) , discrete mathematics , geometry , computer science , artificial intelligence , mathematical analysis
A signed graph Σ consists of a graph and a sign labeling of its edges. A polygon in Σ is “balanced” if its sign product is positiive. A signed graph is “orientatio embedded” in a surface if it is topologically embedded and a polygon is balanced precisely when traveling once around it preserves orientation. We explore the extension to orientation embedding of the ordinary theory of graph embedding. Let d (Σ) be the demigenus (= 2 ‐ x ( S )) of the unique smallest surface S in which Σ has an orientation embedding. Our main results are an easy one, that if Σ has connected components Σ 1 , Σ[2], ⃛, then d (Σ) = d (Σ 1 ) + ⃛, and a hard one, that if Σ has a cut vertex v that splits Σ into Σ 1 , Σ 2 , ⃛, then d (Σ) = d (Σ 1 ) + d (Σ 2 ) + ⃛ ‐δ, where δ depends on the number of Σ i in which v is “loopable”, that is, in which d (Σ i ) = d (Σ i with a negative loop added to v ). This is as with ordinary orientable grpah embedidng except for the existence of the term δ in the cut‐vertex formula. Since loopability is crucial, we give some partial criteria for it. (A complete characterization seems difficult.) We conclude with an application to forbidden subgraphs and minors for orientation embeddability in a given surface. © 1929 John Wiley & Sons, Inc.