CS 39R: Symmetry & Topology
Lecture #7 -- Mon. 3/14, 2016.

PREVIOUS <- - - - > CS 39R HOME < - - - - > CURRENT < - - - - > NEXT

Preparation:

For the non-planar graphs K5, K6, K7 find out what surface of lowest possible genus allows them to be drawn crossing-free.
Bring sketches or models of your solution to class.

Warm-up:

List a few things in your domain of interest where a graph-representation may be useful.

What would be represented by the vertices/nodes and by the edges/links ?

Graph Embeddings

Introduction: The "Utility Graph":
Given 3 utility sources {water, gas, electricity}; the owners of 3 houses in a district with under-grounding
want individual trenches from the 3 utilities to their houses.
What is a good layout?

A complete graph ( K_v ) has exactly one edge between every possible pair of vertices.
K₂ has 1 edge; K₃ has 3 edges; K₄ has 6 edges; K₅ has 10 edges; K_v has v(v-1)/2 edges.

A complete bipartite graph ( K_m,n ) has exactly one edge between every pair of vertices lying two different domains.
K_1,1 has 1 edge; K_1,n has n edges; K_m,2 has 2m edges; K_m,n has m*n edges.

A complete graph ( K_v ) can be embedded crossing-free in a genus g surface: g = ceiling{ (v-3)(v-4)/12 }

A complete bipartite graph ( K_m,n ) can be embedded crossing-free in a genus g surface: g = ceiling (m-2)(n-2)/4 }

Highly symmetrical embedding examples:
K_4,4,4 on a surface of genus 3 (Bridges 2010)
K₁₂ on a surface of genus 6 {Prof. Bokowski's solution} {my early model}

Preview of Proposed Projects

Making a (good) Presentation (after Spring break):

Prepare a brief story that you think will be of interest to your audience -- and fits into less than 10 minutes!
Prepare a 1-minute summary of the main point(s) of your presentation.
Ask yourself: What does the audience already know and what do you need to tell them so that they can understand my story?
What supporting material can make the presentation more interesting -- or easier to understand?

Structure your presentation:
Introduction: Outline the main focal point of your presentation.
Main Part: Tell your story; use your supporting props.
Wrap Up: Repeat the main point(s) that you want your audience to remember.
Knowing that you are well prepared: be confident in your presentation.
Speak slowly, loudly, clearly!

Parameterized Generation of High-Genus Surfaces

"Sculpture Generator I" for Scherk-Collins Toroids

New Homework Assignments:

Due: March 28, 2016
1.) A real design task:

Design a Highway 'Cloverleaf' for a Crossing of Three Highways:
Consider that most of the traffic will probably go straight through the crossing;
but one must still be able to go from any direction to any other direction.
Bridges cost more than roads on the ground.
Use symmetry!

2.) Start doing some research; outline your Course Project Presentation:
State some explicit goals for what you are looking for and how you plan to analyze and use these findings.
Send a one paragraph outline (the 1-minute summary) to me by e-mail before noon on Monday, March 28, 2013.

Have a good Spring Break !