Non-embeddable extensions of embedded minors

DOI10.1016/J.JCTB.2018.01.004MaRDI QIDQ1748267zbMATH OpenOpenAlexFDO

Authors Rajneesh Hegde, Robin Thomas

Publication date 9 May 2018

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.2973

zbMATH Keywords

graph embeddinggraph minornon-planar graph

Mathematics Subject Classification ID

Connectivity (05C40) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph minors (05C83)

Abstract: A graph G is weakly 4-connected if it is 3-connected, has at least five vertices, and for every pair of sets (A,B) with union V(G) and intersection of size three such that no edge has one end in A-B and the other in B-A, one of the induced subgraphs G[A], G[B] has at most four edges. We describe a set of constructions that starting from a weakly 4-connected planar graph G produce a finite list of non-planar weakly 4-connected graphs, each having a minor isomorphic to G, such that every non-planar weakly 4-connected graph H that has a minor isomorphic to G has a minor isomorphic to one of the graphs in the list. Our main result is more general and applies in particular to polyhedral embeddings in any surface.

Recommendations

• Non-planar extensions of subdivisions of planar graphs
• A characterization of weakly four‐connected graphs
• Minors in large almost-5-connected non-planar graphs
• Weak embedding of planar graphs
• Weakly 3-Connected Graphs

Cites work

• A kuratowski theorem for the projective plane
• Excluding minors in nonplanar graphs of girth at least five
• How to Draw a Graph
• Large non-planar graphs and an application to crossing-critical graphs
• Non-planar extensions of subdivisions of planar graphs

Cited in

(3)

• Non-planar extensions of subdivisions of planar graphs
• Minimalp-extensions and the embedding problem
• A characterization of weakly four‐connected graphs

This page was built for publication: Non-embeddable extensions of embedded minors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1748267)