May directed graph be embedded into manifold?

Question

May directed graph be embedded into manifold?How ?and what is the condition?

Answer 1

You can build an embedding inductively, since the complement of a graph in $\mathbb{R}^3$ is path-connected:

Place your vertices at distinct points. Label the edges with some ordering $E_1, E_2,\ldots$, et cetera. Letting $\mathcal{G}_0$ denote the set of vertices, note that $\mathbb{R}^3 \setminus \mathcal{G}_0$ is path-connected. Thus we can represent $E_1$ with a (directed) path that intersects $\mathcal{G}_0$ only at its endpoints. Let $\mathcal{G}_1=\mathcal{G}_0 \cup E_1$. Proceeding inductively, $\mathbb{R}^3 \setminus \mathcal{G}_i$ is path-connected, so we can embed $E_{i+1}$ and define $\mathcal{G}_{i+1}= \mathcal{G}_i \cup E_{i+1}$.

A similar concept (but argued without induction) should hold for infinite graphs.

Answer 2

Hint: Embed in $\mathbb{R}^3.$ Start by drawing it on the $x,y$ plane with crossings OK, but make each crossing only at a point, in a reasonably "nice" way. There are then only finitely many such crossings, and perhaps one can move the edges up/down by a small perturbation to eliminate the crossings. (This is only a hint since I don't know if it can be guaranteed to work.)

Edit: There may be a way to embed in a 2-manifold: Imagine the (finite) graph drawn with thickened lines for its edges, in 3-space, without crossings. This can be done as suggested above provided we thicken the edges which are at that point in 3-space. So far this is a 2-manifold $M$ which contains a copy of the original graph which runs along the "cener lines" of $M.$

Now the idea is to make a copy of the original graph along the 2-d surface $M.$ For each vertex of the original graph one can choose a nearby vertex on $M,$ and then for connected vertices one can draw an arc along $M$ near the edge of the graph which now lies inside $M$.

If this is done, the manifold $M$ will be a sphere with handles attached. Again this idea is a bit sketchy...

Answer 3

As stated in my comment I am unsure of the distinctions that must be made between embedding undirected graphs and directed graphs. To me it seems that to embed a directed graph you just embed the underlying undirected graph then orient the edges (possibly "splitting" an edge in the the case our directed graph has an edge in both directions between two vertices). Please correct me if I am missing some consideration.

As the other answers show a graph can be embedded in $\mathbb{R}^3$, and hence we can always embed a graph in an $n$-manifold for $n \geq 3$. We embed our graph in $\mathbb{R}^3$ then embedd $\mathbb{R}^3$ into $\mathbb{R}^n$ via the canonical embedding. We can then translate and dilate the embedding of our graph so that it lies entirely in some chart. We then map our graph into our manifold and we are done.

For a $2$-manifold Robertson–Seymour theorem tells us we can embed our graph if and only if it does not contain certain "forbidden minors" (which depend on the specific $2$-manifold). The most famous examples are planar graphs, that is graphs which can be embedded in $\mathbb{R}^2$ (or $S^2$). Kuratowski's and Wagner's theorems which tell us the the forbidden minors in this case are $K_5$ and $K_{3,3}$.