Independence ratios of nearly planar graphs
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.
| 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.
Related content
SEE ALSO:
Link this page
Would you like to put a link to this lecture on your homepage?Go ahead! Copy the HTML snippet !


