Subdivisions in planar graphs

DOI10.1006/JCTB.1997.1774MaRDI QIDQ1366603zbMATH OpenOpenAlexFDO

Authors Xingxing Yu

Publication date 15 September 1997

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

Full work available at URL https://doi.org/10.1006/jctb.1997.1774

zbMATH Keywords

connectivitydisjoint pathsplanar graphplane embeddingsubdivisions

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38) Connectivity (05C40)

Review text

Given four distinct vertices in a 4-connected planar graph \(G\), we characterize when the graph \(G\) contains a \(K_4\)-subdivision with the given vertices as its degree three vertices. This result implies the following conjecture of Robertson and Thomas: a 5-connected planar graph has no \(K_4\)-subdivision with specified degree three vertices, if and only if, the four specified vertices are contained in a facial cycle in the unique plane embedding of the graph.

Recommendations

• Partitioning Planar Graphs
• Graph Drawing
• Non-planar extensions of subdivisions of planar graphs
• On the planar subdivision of a drawing of a complete graph in the plane
• Ordinary graphs and subplane partitions
• Subdividing a graph toward a unit-distance graph in the plane
• Subdivisions of graphs: A generalization of paths and cycles
• Path partitions of planar graphs
• Subdivision Drawings of Hypergraphs
• Planarizing graphs and their drawings by vertex splitting

Cites work

• Do 3n − 5 edges force a subdivision ofK5?
• Graph minors. VI. Disjoint paths across a disc
• Graph theory
• Homomorphism theorems for graphs
• Some Homeomorphism Properties of Graphs

Cited in

(16)

• Rooted topological minors on four vertices
• Subdivisions of \(K_5\) in graphs containing \(K_{2,3}\)
• Subdivisions in apex graphs
• Graphs with \(3n-6\) edges not containing a subdivision of \(K_5\)
• Linking four vertices in graphs of large connectivity
• Graphs containing topological H
• Linkage for the diamond and the path with four vertices
• On the planar subdivision of a drawing of a complete graph in the plane
• Non-planar extensions of subdivisions of planar graphs
• scientific article; zbMATH DE number 3941598 (Why is no real title available?)
• scientific article; zbMATH DE number 4033797 (Why is no real title available?)
• scientific article; zbMATH DE number 475620 (Why is no real title available?)
• Subdivisions, parity and well-covered graphs
• Independent paths and \(K_{5}\)-subdivisions
• Planarizing graphs and their drawings by vertex splitting
• Chasing tripods to obtain a rooted subdivision

This page was built for publication: Subdivisions in planar graphs

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