๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

On the orientable genus of graphs embedded in the klein bottle

โœ Scribed by Neil Robertson; Robin Thomas

Publisher
John Wiley and Sons
Year
1991
Tongue
English
Weight
560 KB
Volume
15
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

โœฆ Synopsis

Abstract

Let G be a graph embedded in the Klein bottle with โ€œrepresentativityโ€ at least four. We give a formula for the orientable genus of G, which also implies a polynomially bounded algorithm. The formula is in terms of the number of times certain closed curves on the Klein bottle intersect the graph. In particular, it shows that a cutโ€andโ€paste technique for reโ€embedding graphs is the best possible.

๐Ÿ“œ SIMILAR VOLUMES

Computing the orientable genus of projec
Computing the orientable genus of projective graphs
โœ J. R. Fiedler; J. P. Huneke; R. B. Richter; N. Robertson ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 603 KB

## Abstract The orientable genus is determined for any graph that embeds into the projective plane, ฮฃ, to be essentially half of the representativity of any embedding into ฮฃ. In addition, a structure is given for any 3โ€connected projective planar graph as the union of a spanning planar graph and a

Chords of longest circuits of graphs emb
Chords of longest circuits of graphs embedded in torus and Klein bottle
โœ Xuechao Li; Cun-Quan Zhang ๐Ÿ“‚ Article ๐Ÿ“… 2003 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 177 KB

## Abstract Thomassen conjectured that every longest circuit of a 3โ€connected graph has a chord. It is proved in this paper that every longest circuit of a 4โ€connected graph embedded in a torus or Klein bottle has a chord. ยฉ 2003 Wiley Periodicals, Inc. J Graph Theory 43: 1โ€“23, 2003

Disjoint Cycles in Directed Graphs on th
Disjoint Cycles in Directed Graphs on the Torus and the Klein Bottle
โœ G.L. Ding; A. Schrijver; P.D. Seymour ๐Ÿ“‚ Article ๐Ÿ“… 1993 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 203 KB

We give necessary and sufficient conditions for a directed graph embedded on the torus or the Klein bottle to contain pairwise disjoint circuits, each of a given orientation and homotopy, and in a given order. For the Klein bottle, the theorem is new. For the torus, the theorem was proved before by

Spanning Planar Subgraphs of Graphs in t
Spanning Planar Subgraphs of Graphs in the Torus and Klein Bottle
โœ R. Brunet; M.N. Ellingham; Z.C. Gao; A. Metzlar; R.B. Richter ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 685 KB

There are two main purposes of this article. First we show that every 3-connected graph embedded in the torus or the Klein bottle has a spanning planar subgraph which is 2-connected, and in fact has a slightly stronger connectivity property. Second, this subgraph is applied to show that every 3-conn