Pages

Thursday, 12 September 2013

Planar Graph Drawing Problem

Suppose that $G$ is a planar graph.  Define a convex representation of a graph to be an assignment of each vertex $v$ in $V(G)$ to a convex polygon $p(v)$ so that two vertices $u$ and $v$ are adjacent if and only if $p(u)$ and $p(v)$ intersect only on their boundaries in at least one edge (i.e. so that the polygons share more than just vertices, but the area of their intersection is zero).  Furthermore, suppose that each vertex $v$ in $V(G)$ is assigned some positive number $f(v)$.

Does there exist a convex representation of $G$ so that the area of polygon $p(v)$ is equal to $f(v)$ for all $v$ in $V(G)$?

If $G$ is not 3-connected, then the answer is no, since a graph has a convex representation if and only if $G$ is 3-connected.  An algorithm due to Tutte, applied to the dual graph, will find a convex representation, though it might not be aesthetically pleasing.

Based on the number of area cartograms that have popped up lately, it seems that representation of the graph by polygons with specified areas is also possible, if not all of the time, then most of the time (I've never seen a theorem to that effect, though it does seem plausible).

What asking for, then, is the intersection of both of these ideas.  Like the Tutte embedding, the representation should be convex.  Like the area embedding, the areas of each polygon should have the same size.

No comments :

Post a Comment