Pages

Thursday 19 September 2013

A Few Questions Related to Planar Eulerian Graphs

Let $G$ be an Eulerian graph.  Suppose there is some planar embedding of $G$ in the plane.  When does $G$ have a "non-crossing" Eulerian cycle?  That is to say, if there is a planar drawing of the graph, when can we find an Eulerian cycle in the graph that can be drawn along the edges of the planar drawing without crossing itself?

More generally, suppose that $G$ has $2t$ pairs of odd-degree vertices.  It is known that the edges of $G$ can be decomposed into $t$ paths.  When is there a set of $t$ paths that decompose the edge set of the graph and that can be drawn without crossing themselves or each other?

Even more generally, suppose that $G$ has an embedding into a surface of genus $g$ (or non-orientable genus $g$).  When is there a set of $t$ paths that decompose the edge set of the graph and that can be drawn without crossing themselves or each other?

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.