Graph Miners .XIV. Extending an Embedding

Neil Robertson; P. D. Seymour

doi:10.1006/jctb.1995.1042

Graph Miners .XIV. Extending an Embedding

Neil Robertson, P. D. Seymour

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

13 Scopus citations

Abstract

Let G be a graph, and let H be a subgraph of G drawn in a surface ∑. When can this drawing be extended to an embedding of the whole of G in ∑, up to 3-separations? We show that if such an extension is impossible, and if H is a subdivision of a simple 3-connected graph and is highly “representative”, then one of two obstructions is present. This is a lemma for use in a future paper.

Original language	English (US)
Pages (from-to)	23-50
Number of pages	28
Journal	Journal of Combinatorial Theory, Series B
Volume	65
Issue number	1
DOIs	https://doi.org/10.1006/jctb.1995.1042
State	Published - Sep 1995
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1006/jctb.1995.1042

Cite this

@article{895dc03974bf4afa9d3371dd760da122,

title = "Graph Miners .XIV. Extending an Embedding",

abstract = "Let G be a graph, and let H be a subgraph of G drawn in a surface ∑. When can this drawing be extended to an embedding of the whole of G in ∑, up to 3-separations? We show that if such an extension is impossible, and if H is a subdivision of a simple 3-connected graph and is highly “representative”, then one of two obstructions is present. This is a lemma for use in a future paper.",

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

year = "1995",

month = sep,

doi = "10.1006/jctb.1995.1042",

language = "English (US)",

volume = "65",

pages = "23--50",

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

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - Graph Miners .XIV. Extending an Embedding

AU - Robertson, Neil

AU - Seymour, P. D.

PY - 1995/9

Y1 - 1995/9

N2 - Let G be a graph, and let H be a subgraph of G drawn in a surface ∑. When can this drawing be extended to an embedding of the whole of G in ∑, up to 3-separations? We show that if such an extension is impossible, and if H is a subdivision of a simple 3-connected graph and is highly “representative”, then one of two obstructions is present. This is a lemma for use in a future paper.

AB - Let G be a graph, and let H be a subgraph of G drawn in a surface ∑. When can this drawing be extended to an embedding of the whole of G in ∑, up to 3-separations? We show that if such an extension is impossible, and if H is a subdivision of a simple 3-connected graph and is highly “representative”, then one of two obstructions is present. This is a lemma for use in a future paper.

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

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

U2 - 10.1006/jctb.1995.1042

DO - 10.1006/jctb.1995.1042

M3 - Article

AN - SCOPUS:0011670481

SN - 0095-8956

VL - 65

SP - 23

EP - 50

JO - Journal of Combinatorial Theory, Series B

JF - Journal of Combinatorial Theory, Series B

IS - 1

ER -

Graph Miners .XIV. Extending an Embedding

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this