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?
No comments :
Post a Comment