The projective-planar signed graphs

Thomas Zaslavsky

doi:10.1016/0012-365X(93)90518-X

The projective-planar signed graphs

Thomas Zaslavsky

Mathematics and Statistics

Binghamton University

Research output: Contribution to journal › Article › peer-review

12 Scopus citations

Abstract

We characterize the graphs with distinguished polygons which can be embedded in the projective plane so that the orientation-preserving polygons are just the distinguished ones. These graphs are those whose distinguished polygons are the positive ones in some edge signing of the underlying graph and which either (1) have no link minor isomorphic to any of six particular signed graphs, or equivalently (2) contain no subgraph which is homeomorphic to any of the same six or two other signed graphs. The eight obstruction graphs are, with one trivial exception, derived in simple ways from the planar obstructions K₅ and K_3.3.

Original language	English
Pages (from-to)	223-247
Number of pages	25
Journal	Discrete Mathematics
Volume	113
Issue number	1-3
DOIs	https://doi.org/10.1016/0012-365X(93)90518-X
State	Published - Apr 5 1993

Access to Document

10.1016/0012-365X(93)90518-X

Cite this

@article{895198c5509d47b197aaa0ce3daa4ebd,

title = "The projective-planar signed graphs",

abstract = "We characterize the graphs with distinguished polygons which can be embedded in the projective plane so that the orientation-preserving polygons are just the distinguished ones. These graphs are those whose distinguished polygons are the positive ones in some edge signing of the underlying graph and which either (1) have no link minor isomorphic to any of six particular signed graphs, or equivalently (2) contain no subgraph which is homeomorphic to any of the same six or two other signed graphs. The eight obstruction graphs are, with one trivial exception, derived in simple ways from the planar obstructions K5 and K3.3.",

author = "Thomas Zaslavsky",

year = "1993",

month = apr,

day = "5",

doi = "10.1016/0012-365X(93)90518-X",

language = "English",

volume = "113",

pages = "223--247",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "1-3",

}

TY - JOUR

T1 - The projective-planar signed graphs

AU - Zaslavsky, Thomas

PY - 1993/4/5

Y1 - 1993/4/5

N2 - We characterize the graphs with distinguished polygons which can be embedded in the projective plane so that the orientation-preserving polygons are just the distinguished ones. These graphs are those whose distinguished polygons are the positive ones in some edge signing of the underlying graph and which either (1) have no link minor isomorphic to any of six particular signed graphs, or equivalently (2) contain no subgraph which is homeomorphic to any of the same six or two other signed graphs. The eight obstruction graphs are, with one trivial exception, derived in simple ways from the planar obstructions K5 and K3.3.

AB - We characterize the graphs with distinguished polygons which can be embedded in the projective plane so that the orientation-preserving polygons are just the distinguished ones. These graphs are those whose distinguished polygons are the positive ones in some edge signing of the underlying graph and which either (1) have no link minor isomorphic to any of six particular signed graphs, or equivalently (2) contain no subgraph which is homeomorphic to any of the same six or two other signed graphs. The eight obstruction graphs are, with one trivial exception, derived in simple ways from the planar obstructions K5 and K3.3.

UR - https://www.scopus.com/pages/publications/0039674939

U2 - 10.1016/0012-365X(93)90518-X

DO - 10.1016/0012-365X(93)90518-X

M3 - Article

SN - 0012-365X

VL - 113

SP - 223

EP - 247

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -

The projective-planar signed graphs

Abstract

Access to Document

Other files and links

Fingerprint

Cite this