Independence ratios of nearly planar graphs

author:Michael Albertson, Smith College
published: Sept. 7, 2007,   recorded: September 2007,   views: 149
Categories
You might be experiencing some problems with Your Video player.

Slides

Slides
0:00 - Independence Ratios of Nearly Planar Graphs - Announcement
1:42 Independence Ratios of Nearly Planar Graphs
4:19 Outline
4:29 The Independence Ratio
6:19 Planar Graphs - Page 1
7:10 Planar Graphs - Page 2
8:04 Planar Graphs - Page 3
8:49 Embedded Graphs - Page 1
9:48 Embedded Graphs - Page 2
11:15 Embedded Graphs - Page 3
12:03 Embedded Graphs - Page 4
12:17 Embedded Graphs - Page 5
12:55 On any given S only a few graphs have μ less than 1/4 - Page 1
13:36 On any given S only a few graphs have μ less than 1/4 - Page 2
14:35 Questions for Embedded Graphs - Page 1
15:20 Questions for Embedded Graphs - Page 2
15:33 Questions for Embedded Graphs - Page 3
16:00 Questions for Embedded Graphs - Page 4
16:23 So where are we?
16:57 Where are we going?
17:29 Nearly Planar Graphs
18:02 Thickness
18:56 Independence for Thickness 2 Graphs - Page 1
19:01 - Thickness - Part 2
19:16 - Independence for Thickness 2 Graphs - Page 1 - Part 2
20:16 Independence for Thickness 2 Graphs - Page 2
20:59 Independence for Thickness 2 Graphs (Proof) - Page 3
23:17 Independence for Thickness 2 Graphs - Page 4
23:55 Independence for Thickness 2 Graphs - Page 5
24:21 Crossing Number
25:10 Small Results on Crossings and Colorings [OZ]
26:03 Small Results on Crossings and Colorings [A]
27:38 Small Results on Crossings and Colorings - Remark
28:46 Small Results on Crossings and Colorings - Theorem
29:26 Small Results on Crossings and Colorings - Theorem / Proof
30:27 Small Results on Crossings and Colorings - Theorem / Remark
30:29 A Naive Definition of Locally Planar
31:27 Locally Planar Embedded Graphs - Definition
32:02 Locally Planar Embedded Graphs - Theorems
32:45 A Question on Local Planarity and Thickness
33:44 New Nearly Planar Graphs
34:11 Another Version of Locally Planar - Page 1
35:26 Another Version of Locally Planar - Page 2
35:36 Another Version of Locally Planar - Page 3
35:44 Another Version of Locally Planar - Page 4
35:50 Another Version of Locally Planar - Page 5
36:02 Quasi Planar Graphs - Page 1
36:43 Quasi Planar Graphs - Page 2
37:17 Quasi Planar Graphs - Page 3
38:12 Quasi Planar Graphs - Page 4
38:43 Quasi Planar Graphs - Page 5
39:13 Quasi Planar Graphs - Page 6
39:20 Quasi Planar Graphs - Page 7
40:08 Quasi Planar Graphs - Page 8
40:35 Quasi Planar Graphs - Page 9
40:52 Quasi Planar Graphs - Page 10
41:23 Quasi Planar Graphs - Page 12
41:45 Quasi Planar Graphs - Page 13
42:24 An Alternate Definition of Q-P - Page 1
43:17 An Alternate Definition of Q-P - Page 2
43:23 An Alternate Definition of Q-P - Page 3
43:35 An Alternate Definition of Q-P - Page 4
43:42 An Alternate Definition of Q-P - Page 5
44:39 - Independence Ratios of Nearly Planar Graphs - Questions

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.

We are currently conducting a short survey. We value your feedback, and would appreciate if you took a few moments to respond to some questions. Click here to take the survey.

Description

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.

Link this page  

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: