Nested cycles in large triangulations and crossing-critical graphs

Details Nested cycles in large triangulations and crossing-critical graphs Nested cycles in large triangulations and crossing-critical graphs

2009-11-24

arxiv.org/abs/0911.4690v1

Mathematics

Combinatorics

Scientific paper

We show that every sufficiently large plane triangulation has a large collection of nested cycles that either are pairwise disjoint, or pairwise intersect in exactly one vertex, or pairwise intersect in exactly two vertices. We apply this result to show that for each fixed positive integer $k$, there are only finitely many $k$-crossing-critical simple graphs of average degree at least six. Combined with the recent constructions of crossing-critical graphs given by Bokal, this settles the question of for which numbers $q>0$ there is an infinite family of $k$-crossing-critical simple graphs of average degree $q$.

Affiliated with

Also associated with

No associations

Rating

Nested cycles in large triangulations and 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 Nested cycles in large triangulations and crossing-critical graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Nested cycles in large triangulations and crossing-critical graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-280315