event thumbnail image
Pascal Workshop on Graph Theory and Machine Learning
Pascal

Independence ratios of nearly planar graphs

author: Michael Albertson, Smith College

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.

You might be experiencing some problems with Your Video player.
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

Lecture rating

People found this lecture:
Worth seeing
because it is:
 Valuable and informative
Well presented
Easily understandable
Acceptably recorded
You need to login to cast your vote.

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.

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: