Paper Info
Title
Orientation embedding of signed graphs
Abstract
A signed graph SIGMA consists of a graph and a sign labeling of its edges. A polygon in SIGMA is "balanced" if its sign product is positive. A signed graph is "orientation 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(SIGMA) be the demigenus (= 2 - chi(S)) of the unique smallest surface S in which SIGMA has an orientation embedding. Our main results are an easy one, that if SIGMA has connected components SIGMA1, SIGMA2,..., then d(SIGMA) = d(SIGMA1) + d(SIGMA2) + ..., and a hard one, that if SIGMA has a cut vertex v that splits SIGMA into SIGMA1, SIGMA2,..., then d(SIGMA) = d(SIGMA1) + d(SIGMA2) + ... -delta, where delta depends on the number of SIGMA(i) in which v is "loopable," that is, in which d(SIGMA(i)) = d(SIGMA(i) with a negative loop added to v). This is as with ordinary orientable graph embedding except for the existence of the term delta 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.
Year
DOI
Venue
1992
10.1002/jgt.3190160503
Journal of Graph Theory
Keywords
DocType
Volume
orientation embedding
Journal
16
Issue
ISSN
Citations 
5
0364-9024
8
PageRank 
References 
Authors
1.04
9
1
Name
Order
Citations
PageRank
T. Zaslavsky129756.67