Papadimitriou – Code for Food

Hi all,

The second Theory Weekly Meeting will happen this Friday between 4:00 – 5:00 pm at 203 Davis Hall(Theory Lab). The schedule will be as follows :

4:00 – 4:50 pm – A talk by Prof. Roger(Xin) He.

The abstract in his own words :

Two “graph drawing” problems –

Given a graph G, the general idea of “graph drawing” is to draw G on the plane so that certain conditions/optimization measures are met. Depending on thees conditions, these problems can be fairly practical, or very theoretical. The tools involved are often graph-theoretic. Sometimes, there are geometry flavor in it. (Since we are talking about the drawings on the plane, most interesting stuff are for planar graphs.)

I’ll be discussing two such problems, (towards theoretical end), that I and my students have studied/are doing.

Definition 1: Given a planar graph G and a metric function $D(*,*)$ , a “greedy drawing” of G is:
1. Each vertex of G is drawn as a point on the plane.
2. Each edge of G is drawn as a straight line connecting its two end vertices.
3. Satisfies the “greedy drawing” condition: For any two vertices u, w in G, there exits a neighbor v of w, such that D(v,w) < D(u,w). (In other words, v is closer to w than u.)

The condition 3 is equivalent to the following: For any two vertices u,w in G, there is a path $P_{uw}$ , such that, when traveling from u to w, the distance D(x,w) between the intermediate vertices x of $P_{uw}$ to w strictly decreases.

The problem is motivated by a network routing problem. If G has a greedy drawing, we will have a very simple routing protocol: If u wants to send a message to the destination w, u can simply send it to a neighbor v, that is closer to w than itself. (Then v will follow the same protocol. The greedy property guarantees the message will reach the destination w).

The questions are: Which class of graphs has such drawings? If so, what’s the smallest size of the drawing.

A (moderately famous) related conjecture (now theorem) is (Papadimitriou, 2003): Every 3-connected plane graph G has a greedy drawing with respect to Euclidean distance $D(*,*)$ . The conjecture was proved by Tom Leighton et. al.(2008). However, there there drawbacks and open problems, which we will discuss.

Another problem:

Def 2: Same as Def 1, except that the condition 3 is replaced by the following. Condition 3 satisfies the “monotone condition”: For any two vertices u,w, there is a path $P_{uw}$ from u to w, and a line (or direction) $l_{uw}$ , such that $P_{uw}$ is “monotone with respect $l_{uw}$ ” (namely, the order of the projection points of the vertices of $P_{uw}$ on the direction $l_{uw}$ is the same order of the vertices in $P_{uw}$ ).

This drawing style is introduced 3 years ago, partially to address the drawbacks of “greedy drawing”. The questions are: Which class of graphs has such drawings? If so, what’s the smallest size of the drawing.
I’ll discuss partial results, and related problems.

4:50 – 5:00 pm – Socializing with the Theory community.

All are welcome!