UB Theory Weekly – Week 2

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!


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s