Subdivisions in Planar Graphs
Copyright policy )Subdivisions in Planar Graphs
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.
- GEORGIA TECH RESEARCH CORPORATION United States
- Georgia Institute of Technology United States
Connectivity, disjoint paths, Computational Theory and Mathematics, subdivisions, connectivity, plane embedding, planar graph, Discrete Mathematics and Combinatorics, Paths and cycles, Planar graphs; geometric and topological aspects of graph theory, Theoretical Computer Science
Connectivity, disjoint paths, Computational Theory and Mathematics, subdivisions, connectivity, plane embedding, planar graph, Discrete Mathematics and Combinatorics, Paths and cycles, Planar graphs; geometric and topological aspects of graph theory, Theoretical Computer Science
citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).11 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!