Material Detail

Independence ratios of nearly planar graphs

Independence ratios of nearly planar graphs

This video was recorded at 6th Slovenian International Conference on Graph Theory, Bled 2007. With purposeful imprecision, a graph is said to be nearly planar if it resembles in some essential way a planar graph. Classic measures of near planarity include the thickness, the crossing number, and the genus. Modern versions of nearly planar graphs include the graphs embedded on surfaces with large width (shortest noncontractible cycle). Geometric graph theory has given us a different notion of locally planar as well as two definitions of quasi-planar graphs. This talk will begin with a retrospective look at independence ratios of locally planar graphs. We consider contrasts between results about the independence ratio and those about the chromatic number. We will then proceed to results and open questions about independence ratios of various classes of nearly planar graphs.

Quality

  • User Rating
  • Comments
  • Learning Exercises
  • Bookmark Collections
  • Course ePortfolios
  • Accessibility Info

More about this material

Comments

Log in to participate in the discussions or sign up if you are not already a MERLOT member.