event thumbnail image
Invited Speakers

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.

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: