Geometry of partial cube graphs
author:
David Eppstein,
University of California, Irvine
Description
Partial cubes are graphs defined by a geometric structure: the graph vertices can be
placed on the vertices of a hypercube in such a way that graph distance equals Hamming
distance. We survey recent developments in the theory of these graphs that relate them
in other ways to geometric structures: lattice embeddings, hyperplane arrangements,
systems of translated quadrants in the plane, and flip graphs of triangulations.
You might be experiencing some problems with Your Video player.
| Slides | |
| 0:00 | - Geometry of Partial Cubes - Announcement |
| 0:31 | Geometry of Partial Cubes |
| 0:33 | Outline |
| 0:38 | Outline - Definitions |
| 0:42 | Context: Geometric graphs and metric embedding - Page 1 |
| 1:36 | Context: Geometric graphs and metric embedding - Page 2 |
| 1:47 | Partial cubes as geometric graphs |
| 3:11 | Graph-theoretic characterization |
| 4:47 | Automaton-theoretic characterization |
| 6:15 | Fundamental components of a partial cube |
| 7:31 | Outline - Examples |
| 7:54 | Partial cubes from hyperplane arrangements |
| 10:39 | Acyclic orientations of an undirected graph |
| 12:52 | Weak orders |
| 13:30 | Antimatroids |
| 16:09 | Integer partitions |
| 16:18 | Outline - Dimension |
| 16:25 | Concepts of dimension for partial cubes |
| 18:47 | Tree dimension |
| 20:45 | Tree dimension as graph coloring |
| 21:12 | Lattice dimension |
| 22:15 | Lattice dimension of trees |
| 23:30 | Lattice embeddings as paths of semicubes |
| 26:52 | Characterizing lattice dimension |
| 27:27 | Outline - Graph Drawing |
| 27:34 | Graph drawing desiderata |
| 29:01 | Visualize partial cube by projecting lattice embedding |
| 30:10 | Planar projection of three-dimensional lattices |
| 31:31 | Planar graphs with centrally-symmetric faces |
| 31:47 | - Planar projection of three-dimensional lattices - Part 2 |
| 31:53 | - Planar graphs with centrally-symmetric faces - Part 2 |
| 33:31 | Examples of planar graphs with centrally-symmetric faces |
| 34:25 | Arrangement of translates of a wedge |
| 35:25 | Upright-quad drawing |
| 36:43 | Outline - Cubic Partial Cubes |
| 37:00 | Cubic (3-regular) partial cubes |
| 38:36 | Cubic partial cubes from simplicial arrangements |
| 41:35 | Infinite families of cubic partial cubes |
| 44:14 | Additional sporadic cubic partial cubes |
| 44:34 | Connection to symmetric-face planar drawing |
| 45:10 | sicgt07_eppSometimes, connecting two different drawings works |
| 45:43 | Summary of progress on cubic partial cubes |
| 45:56 | Outline - Flip Distance |
| 46:21 | Flip graphs of point sets |
| 48:25 | Delaunay triangulation |
| 49:45 | The quadrilateral graph of a point set |
| 50:10 | Flip graphs and partial cubes |
| 51:32 | Point sets with no empty pentagon |
| 51:53 | Conclusions: Geometry and partial cubes |
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
Visitors who watched this lecture also watched...
Link this page
Would you like to put a link to this lecture on your homepage?Go ahead! Copy the HTML snippet !





