Graph Minors: XVII. Taming a Vortex

Neil Robertson; P. D. Seymour

doi:10.1006/jctb.1999.1919

Graph Minors: XVII. Taming a Vortex

Neil Robertson, P. D. Seymour

Mathematics

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

30 Scopus citations

Abstract

The main result of this series serves to reduce several problems about general graphs to problems about graphs which can "almost" be drawn in surfaces of bounded genus. In applications of the theorem we usually need to encode such a nearly embedded graph as a hypergraph which can be drawn completely in the surface. The purpose of this paper is to show how to "tidy up" near-embeddings to facilitate the encoding procedure.

Original language	English (US)
Pages (from-to)	162-210
Number of pages	49
Journal	Journal of Combinatorial Theory. Series B
Volume	77
Issue number	1
DOIs	https://doi.org/10.1006/jctb.1999.1919
State	Published - Sep 1999

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1006/jctb.1999.1919

Cite this

@article{c8317abe079f45abaf63a571c34954cf,

title = "Graph Minors: XVII. Taming a Vortex",

abstract = "The main result of this series serves to reduce several problems about general graphs to problems about graphs which can {"}almost{"} be drawn in surfaces of bounded genus. In applications of the theorem we usually need to encode such a nearly embedded graph as a hypergraph which can be drawn completely in the surface. The purpose of this paper is to show how to {"}tidy up{"} near-embeddings to facilitate the encoding procedure.",

author = "Neil Robertson and Seymour, {P. D.}",

note = "Funding Information: * This research was partially supported by NSF grant DMS 8504054 and was partially performed under a consulting agreement with Bellcore.",

year = "1999",

month = sep,

doi = "10.1006/jctb.1999.1919",

language = "English (US)",

volume = "77",

pages = "162--210",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - Graph Minors

T2 - XVII. Taming a Vortex

AU - Robertson, Neil

AU - Seymour, P. D.

N1 - Funding Information: * This research was partially supported by NSF grant DMS 8504054 and was partially performed under a consulting agreement with Bellcore.

PY - 1999/9

Y1 - 1999/9

N2 - The main result of this series serves to reduce several problems about general graphs to problems about graphs which can "almost" be drawn in surfaces of bounded genus. In applications of the theorem we usually need to encode such a nearly embedded graph as a hypergraph which can be drawn completely in the surface. The purpose of this paper is to show how to "tidy up" near-embeddings to facilitate the encoding procedure.

AB - The main result of this series serves to reduce several problems about general graphs to problems about graphs which can "almost" be drawn in surfaces of bounded genus. In applications of the theorem we usually need to encode such a nearly embedded graph as a hypergraph which can be drawn completely in the surface. The purpose of this paper is to show how to "tidy up" near-embeddings to facilitate the encoding procedure.

UR - http://www.scopus.com/inward/record.url?scp=0039257348&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0039257348&partnerID=8YFLogxK

U2 - 10.1006/jctb.1999.1919

DO - 10.1006/jctb.1999.1919

M3 - Article

AN - SCOPUS:0039257348

SN - 0095-8956

VL - 77

SP - 162

EP - 210

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 1

ER -

Graph Minors: XVII. Taming a Vortex

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this