Large Non-Planar Graphs and an Application to Crossing-Critical Graphs

Details Large Non-Planar Graphs and an Application to Crossing-Critical Graphs Large Non-Planar Graphs and an Application to Crossing-Critical Graphs

2009-12-24

arxiv.org/abs/0912.4778v2

Mathematics

Combinatorics

To appear in Journal of Combinatorial Theory B. 20 pages. No figures. TeX

Scientific paper

We prove that, for every positive integer k, there is an integer N such that every 4-connected non-planar graph with at least N vertices has a minor isomorphic to K_{4,k}, the graph obtained from a cycle of length 2k+1 by adding an edge joining every pair of vertices at distance exactly k, or the graph obtained from a cycle of length k by adding two vertices adjacent to each other and to every vertex on the cycle. We also prove a version of this for subdivisions rather than minors, and relax the connectivity to allow 3-cuts with one side planar and of bounded size. We deduce that for every integer k there are only finitely many 3-connected 2-crossing-critical graphs with no subdivision isomorphic to the graph obtained from a cycle of length 2k by joining all pairs of diagonally opposite vertices.

Affiliated with

Also associated with

No associations

Rating

Large Non-Planar Graphs and an Application to Crossing-Critical Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Large Non-Planar Graphs and an Application to Crossing-Critical Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Large Non-Planar Graphs and an Application to Crossing-Critical Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-554993