I know any finite graph can be embedded in a surface of high enough genus. However, there are infinite graphs that cannot be embedded into any surface or $\mathbb{R}^3$, simply because the graph has more points than the continuum.
Let $T$ be a topological space. A (directed multi)graph $H=(V,E,S,T)$ is called a $T$-drawing if $V\subseteq T$ and any edge $e\in E$ is a topological path between its incident vertices, i.e. a continuous function $e:[0,1]\rightarrow T$ with $e.0=S.e$ and $e.1=T.e$. $H$ is called a clean $T$-drawing if it fulfills the additional requirements:
- An edge cannot cross itself except possibly at its endpoints.
- An edge cannot run over vertices it isn't incident with.
- At most two edges can cross at a point of $T$ that is not an endpoint of any of the edges.
Let $G$ be a (directed multi)graph. A topological space $T$ is called $G$-spacious if there exists a $T$-drawing $H$ such that $G$ and $H$ are isomorphic. If $H$ is additionally clean, $T$ is also called clean.
(The definitions above were formulated by myself.)
Let $S$ be a surface (i.e. a 2-dimensional manifold). A clean $S$-drawing $H$ is what's commonly known as a drawing of a graph. If additionally no two edges of $H$ cross except possibly at their endpoints, $H$ is known as the embedding of a graph (on the surface $S$). A graph $G$ (usually assumed finite) is said to be embedable on the surface $S$ iff $S$ admits an embedding of $H$. This is what most literature works with.
Question: Does for any (directed multi)graph $G$ (of arbitrary cardinality) exist a $G$-spacious topological space $T$, additionally such that $T$ is clean or even admits an embedding?
I know some classic results:
- $\mathbb{R}^2$ is clean $G$-spacious for any finite graph $G$ and some countable graphs. The graphs for which $\mathbb{R}^2$ even admits embeddings are usually called planar.
- For every finite graph $G$ there exists a surface $S$ such that $S$ admits an embedding of $G$.
- $\mathbb{R}^3$ is clean $G$-spacious for any finite graph $G$ and some countable graphs and admits embeddings for all finite graphs (e.g. with vertices on the Image of the curve $\gamma:\mathbb{R}\rightarrow\mathbb{R}^3$, $\gamma(t)=(t,t^2,t^3)$.
On the other hand, it is easy to think of graphs $G$ such that $\mathbb{R}^n$ isn't $G$-spacious for any $n\in\mathbb{N}$. For example take the simple graph $G=(V,E)$ with $V=2^\mathbb{R}$ and $\{A,B\}\in E$ iff $A\triangle B$ (symmetric difference) is finite. Since $|2^\mathbb{R}|>|\mathbb{R}^n|$ no $G$-isomorphic graph $H$ can ever be a $\mathbb{R}^n$-drawing.
All topologies I can visually image are embeddable somehow in $\mathbb{R}^n$ and while I know that topologies with more points than the continuum must exist (since metrics and norms on function spaces induce topologies), I cannot fathom how they look like or if they would be $G$-spacious. I am aware that I can always create a bigger graph by my construction above with $T$ instead of $\mathbb{R}$, so in a sense there is no "universial" topology for embedding any graph, although there might one for each class of graphs with bounded cardinality, like $\mathbb{R}^3$ is one for the finite graphs.
Own attempt
Since, as I mentioned, I'm unfamiliar with topology of higher cardinality, my only attempts were trying the discrete and trivialtopology on the set of vertices. The discrete cannot work, since I can't have continuous paths here, and the trivial works at least for simple (di)graphs with arbitary cardinality: Any path is continuous here, so for any edge $e$ of $G=(V,E,S,T)$ choose $p_e:[0,1]\rightarrow V$ such that $p_e(x)= S.e$ if $x<0.5$ and $p_e(x)=T.e$ else. This can also easily be generalized to graphs were each edge multiplicity is at most countable.
There is in fact a standard way to turn any graph into a topological space in which it "embeds" rather tautologically. Start with the space $X=V\coprod E\times[0,1]$, where you give $V$ and $E$ the discrete topology. Then let $T$ be the quotient of $X$ by the equivalence relation $\sim$ generated by saying $v\sim(e,0)$ and $w\sim(e,1)$ for each edge $e\in E$ which goes from a vertex $v$ to a vertex $w$. Each edge then becomes a path in $T$, namely the composition of the path $t\mapsto (e,t)$ in $X$ with the quotient map $X\to T$. No edges ever cross (except at endpoints that they share), since these paths are all disjoint in $X$ and our equivalence relation only identified the endpoints.
This construction is used all the time in topology (in particular, graphs in this sense are exactly the same as 1-dimensional CW-complexes). You can find some more information on Wikipedia, for instance.