Mixing
Infinite graph is planar iff it can be embedded in sphere
Clash Royale CLAN TAG#URR8PPP
up vote
6
down vote
favorite
My question is about the following statement about planar graphs:
A graph is planar (i.e. can be embedded in the plane) if and only if it can be embedded in the sphere $S^2$.
By an embedding we mean the following:
To every vertex $v in V$ we associate a unique point in $mathbbR^2$(or $S^2$). To every edge $e in G$ we associate a unique simple arc, which is a homeomorphic image of $[0,1]$, connecting the points associated to its end vertices such that no two arcs intersect other than in a common vertex point.
The "only if" part of the statement above follows directly by using stereographic projection, which gives an embedding $mathbbR^2 hookrightarrow S^2$.
For the "if" part, in every proof I find one simply says that in an embedding of a graph in $S^2$, one can always avoid a point and can therefore use stereographic projection again to get the embedding in $mathbbR^2$.
I can see this fact being true for finite graphs, as the embedded graph is just the bijective continuous image of finitely many intervals glued together in some way (which is a compact space), so if the image was the whole $S^2$, we would get a homeomorphism between $S^2$ and something which isn't $S^2$.
But what about infinite graphs? As far as I know, a graph is just defined to be a tuple $(V,E)$, where $V$ is a set (of vertices) and $E$ is a set consisting of some 2-element-subsets of $V$.
So $V$ can be basically anything, so I could for example just take $V = S^2$ (as a set), or any other (uncountable) infinite set.
In this case, how can I ensure that in a drawing of the graph on $S^2$ I can still avoid one point? Or is this statement not even true for infinite graphs?
general-topology graph-theory planar-graph topological-graph-theory
edited Jul 31 at 15:23
Ed Pegg
9,12432486
asked Jul 31 at 15:17
TilBe
313
 |Â
show 6 more comments
up vote
6
down vote
favorite
My question is about the following statement about planar graphs:
A graph is planar (i.e. can be embedded in the plane) if and only if it can be embedded in the sphere $S^2$.
By an embedding we mean the following:
To every vertex $v in V$ we associate a unique point in $mathbbR^2$(or $S^2$). To every edge $e in G$ we associate a unique simple arc, which is a homeomorphic image of $[0,1]$, connecting the points associated to its end vertices such that no two arcs intersect other than in a common vertex point.
The "only if" part of the statement above follows directly by using stereographic projection, which gives an embedding $mathbbR^2 hookrightarrow S^2$.
For the "if" part, in every proof I find one simply says that in an embedding of a graph in $S^2$, one can always avoid a point and can therefore use stereographic projection again to get the embedding in $mathbbR^2$.
I can see this fact being true for finite graphs, as the embedded graph is just the bijective continuous image of finitely many intervals glued together in some way (which is a compact space), so if the image was the whole $S^2$, we would get a homeomorphism between $S^2$ and something which isn't $S^2$.
But what about infinite graphs? As far as I know, a graph is just defined to be a tuple $(V,E)$, where $V$ is a set (of vertices) and $E$ is a set consisting of some 2-element-subsets of $V$.
So $V$ can be basically anything, so I could for example just take $V = S^2$ (as a set), or any other (uncountable) infinite set.
In this case, how can I ensure that in a drawing of the graph on $S^2$ I can still avoid one point? Or is this statement not even true for infinite graphs?
general-topology graph-theory planar-graph topological-graph-theory
edited Jul 31 at 15:23
Ed Pegg
9,12432486
asked Jul 31 at 15:17
TilBe
313
1
Sure...you could say that there's an edge from $P$ to $Q$ exactly when they're antipodal, for instance. The usual definition of a graph embedding seems to take into account a kind of topology on the geometric realization of the graph, and that topology doesn't seem to be related (in the case of a graph with all points of $S^2$ as vertices, and no edges) to the topology of the underlying space $S^2$. So using $S^2$ seems like a red herring --- any uncountable set would work equally well.
– John Hughes
Jul 31 at 15:47
2
Henning Makholm's answer to this related question -- math.stackexchange.com/questions/712013/… -- seems very relevant.
– John Hughes
Jul 31 at 15:54
1
Your definition of "embedding" is not what I would consider to be the normal definition of an embedding for an infinite graph. Any graph naturally gives rise to a topological space (just the quotient space obtained by gluing together all its vertices and edges). Your definition is equivalent to a continuous injection from this topological space, rather than a topological embedding.
– Eric Wofsey
Jul 31 at 18:44
1
Assuming you have some awful "embedding" (as Eric says, not really an embedding in the normal sense" where vertices are dense and every point is in the image, you can still get it to be planar. For example, take stereographic projection such that some point lying in an edge is sent to $infty$. Then map the plane by homeomorphism to a smaller simply connected subset of the plane (like a disk). You can now connect the cut edge back up in the complement of that disk to get a planar "embedding"
– Carl
Aug 1 at 2:21
1
And of course, if every point of the sphere is a vertex, then you use axiom of choice/ cardinality arguments to shift some infinite sequence of points so that some point is no longer in the image.
– Carl
Aug 1 at 2:22
 |Â
show 6 more comments
up vote
6
down vote
favorite
up vote
6
down vote
favorite
My question is about the following statement about planar graphs:
A graph is planar (i.e. can be embedded in the plane) if and only if it can be embedded in the sphere $S^2$.
By an embedding we mean the following:
To every vertex $v in V$ we associate a unique point in $mathbbR^2$(or $S^2$). To every edge $e in G$ we associate a unique simple arc, which is a homeomorphic image of $[0,1]$, connecting the points associated to its end vertices such that no two arcs intersect other than in a common vertex point.
The "only if" part of the statement above follows directly by using stereographic projection, which gives an embedding $mathbbR^2 hookrightarrow S^2$.
For the "if" part, in every proof I find one simply says that in an embedding of a graph in $S^2$, one can always avoid a point and can therefore use stereographic projection again to get the embedding in $mathbbR^2$.
I can see this fact being true for finite graphs, as the embedded graph is just the bijective continuous image of finitely many intervals glued together in some way (which is a compact space), so if the image was the whole $S^2$, we would get a homeomorphism between $S^2$ and something which isn't $S^2$.
But what about infinite graphs? As far as I know, a graph is just defined to be a tuple $(V,E)$, where $V$ is a set (of vertices) and $E$ is a set consisting of some 2-element-subsets of $V$.
So $V$ can be basically anything, so I could for example just take $V = S^2$ (as a set), or any other (uncountable) infinite set.
In this case, how can I ensure that in a drawing of the graph on $S^2$ I can still avoid one point? Or is this statement not even true for infinite graphs?
general-topology graph-theory planar-graph topological-graph-theory
edited Jul 31 at 15:23
Ed Pegg
9,12432486
asked Jul 31 at 15:17
TilBe
313
My question is about the following statement about planar graphs:
A graph is planar (i.e. can be embedded in the plane) if and only if it can be embedded in the sphere $S^2$.
By an embedding we mean the following:
To every vertex $v in V$ we associate a unique point in $mathbbR^2$(or $S^2$). To every edge $e in G$ we associate a unique simple arc, which is a homeomorphic image of $[0,1]$, connecting the points associated to its end vertices such that no two arcs intersect other than in a common vertex point.
The "only if" part of the statement above follows directly by using stereographic projection, which gives an embedding $mathbbR^2 hookrightarrow S^2$.
For the "if" part, in every proof I find one simply says that in an embedding of a graph in $S^2$, one can always avoid a point and can therefore use stereographic projection again to get the embedding in $mathbbR^2$.
I can see this fact being true for finite graphs, as the embedded graph is just the bijective continuous image of finitely many intervals glued together in some way (which is a compact space), so if the image was the whole $S^2$, we would get a homeomorphism between $S^2$ and something which isn't $S^2$.
But what about infinite graphs? As far as I know, a graph is just defined to be a tuple $(V,E)$, where $V$ is a set (of vertices) and $E$ is a set consisting of some 2-element-subsets of $V$.
So $V$ can be basically anything, so I could for example just take $V = S^2$ (as a set), or any other (uncountable) infinite set.
In this case, how can I ensure that in a drawing of the graph on $S^2$ I can still avoid one point? Or is this statement not even true for infinite graphs?
general-topology graph-theory planar-graph topological-graph-theory
edited Jul 31 at 15:23
Ed Pegg
9,12432486
asked Jul 31 at 15:17
TilBe
313
edited Jul 31 at 15:23
Ed Pegg
9,12432486
edited Jul 31 at 15:23
Ed Pegg
9,12432486
edited Jul 31 at 15:23
Ed Pegg
9,12432486
9,12432486
asked Jul 31 at 15:17
TilBe
313
asked Jul 31 at 15:17
TilBe
313
asked Jul 31 at 15:17
TilBe
313
313
1
Sure...you could say that there's an edge from $P$ to $Q$ exactly when they're antipodal, for instance. The usual definition of a graph embedding seems to take into account a kind of topology on the geometric realization of the graph, and that topology doesn't seem to be related (in the case of a graph with all points of $S^2$ as vertices, and no edges) to the topology of the underlying space $S^2$. So using $S^2$ seems like a red herring --- any uncountable set would work equally well.
– John Hughes
Jul 31 at 15:47
2
Henning Makholm's answer to this related question -- math.stackexchange.com/questions/712013/… -- seems very relevant.
– John Hughes
Jul 31 at 15:54
1
Your definition of "embedding" is not what I would consider to be the normal definition of an embedding for an infinite graph. Any graph naturally gives rise to a topological space (just the quotient space obtained by gluing together all its vertices and edges). Your definition is equivalent to a continuous injection from this topological space, rather than a topological embedding.
– Eric Wofsey
Jul 31 at 18:44
1
Assuming you have some awful "embedding" (as Eric says, not really an embedding in the normal sense" where vertices are dense and every point is in the image, you can still get it to be planar. For example, take stereographic projection such that some point lying in an edge is sent to $infty$. Then map the plane by homeomorphism to a smaller simply connected subset of the plane (like a disk). You can now connect the cut edge back up in the complement of that disk to get a planar "embedding"
– Carl
Aug 1 at 2:21
1
And of course, if every point of the sphere is a vertex, then you use axiom of choice/ cardinality arguments to shift some infinite sequence of points so that some point is no longer in the image.
– Carl
Aug 1 at 2:22
 |Â
show 6 more comments
1
Sure...you could say that there's an edge from $P$ to $Q$ exactly when they're antipodal, for instance. The usual definition of a graph embedding seems to take into account a kind of topology on the geometric realization of the graph, and that topology doesn't seem to be related (in the case of a graph with all points of $S^2$ as vertices, and no edges) to the topology of the underlying space $S^2$. So using $S^2$ seems like a red herring --- any uncountable set would work equally well.
– John Hughes
Jul 31 at 15:47
2
Henning Makholm's answer to this related question -- math.stackexchange.com/questions/712013/… -- seems very relevant.
– John Hughes
Jul 31 at 15:54
1
Your definition of "embedding" is not what I would consider to be the normal definition of an embedding for an infinite graph. Any graph naturally gives rise to a topological space (just the quotient space obtained by gluing together all its vertices and edges). Your definition is equivalent to a continuous injection from this topological space, rather than a topological embedding.
– Eric Wofsey
Jul 31 at 18:44
1
Assuming you have some awful "embedding" (as Eric says, not really an embedding in the normal sense" where vertices are dense and every point is in the image, you can still get it to be planar. For example, take stereographic projection such that some point lying in an edge is sent to $infty$. Then map the plane by homeomorphism to a smaller simply connected subset of the plane (like a disk). You can now connect the cut edge back up in the complement of that disk to get a planar "embedding"
– Carl
Aug 1 at 2:21
1
And of course, if every point of the sphere is a vertex, then you use axiom of choice/ cardinality arguments to shift some infinite sequence of points so that some point is no longer in the image.
– Carl
Aug 1 at 2:22
1
1
Sure...you could say that there's an edge from $P$ to $Q$ exactly when they're antipodal, for instance. The usual definition of a graph embedding seems to take into account a kind of topology on the geometric realization of the graph, and that topology doesn't seem to be related (in the case of a graph with all points of $S^2$ as vertices, and no edges) to the topology of the underlying space $S^2$. So using $S^2$ seems like a red herring --- any uncountable set would work equally well.
– John Hughes
Jul 31 at 15:47
Sure...you could say that there's an edge from $P$ to $Q$ exactly when they're antipodal, for instance. The usual definition of a graph embedding seems to take into account a kind of topology on the geometric realization of the graph, and that topology doesn't seem to be related (in the case of a graph with all points of $S^2$ as vertices, and no edges) to the topology of the underlying space $S^2$. So using $S^2$ seems like a red herring --- any uncountable set would work equally well.
– John Hughes
Jul 31 at 15:47
2
2
Henning Makholm's answer to this related question -- math.stackexchange.com/questions/712013/… -- seems very relevant.
– John Hughes
Jul 31 at 15:54
Henning Makholm's answer to this related question -- math.stackexchange.com/questions/712013/… -- seems very relevant.
– John Hughes
Jul 31 at 15:54
1
1
Your definition of "embedding" is not what I would consider to be the normal definition of an embedding for an infinite graph. Any graph naturally gives rise to a topological space (just the quotient space obtained by gluing together all its vertices and edges). Your definition is equivalent to a continuous injection from this topological space, rather than a topological embedding.
– Eric Wofsey
Jul 31 at 18:44
Your definition of "embedding" is not what I would consider to be the normal definition of an embedding for an infinite graph. Any graph naturally gives rise to a topological space (just the quotient space obtained by gluing together all its vertices and edges). Your definition is equivalent to a continuous injection from this topological space, rather than a topological embedding.
– Eric Wofsey
Jul 31 at 18:44
1
1
Assuming you have some awful "embedding" (as Eric says, not really an embedding in the normal sense" where vertices are dense and every point is in the image, you can still get it to be planar. For example, take stereographic projection such that some point lying in an edge is sent to $infty$. Then map the plane by homeomorphism to a smaller simply connected subset of the plane (like a disk). You can now connect the cut edge back up in the complement of that disk to get a planar "embedding"
– Carl
Aug 1 at 2:21
Assuming you have some awful "embedding" (as Eric says, not really an embedding in the normal sense" where vertices are dense and every point is in the image, you can still get it to be planar. For example, take stereographic projection such that some point lying in an edge is sent to $infty$. Then map the plane by homeomorphism to a smaller simply connected subset of the plane (like a disk). You can now connect the cut edge back up in the complement of that disk to get a planar "embedding"
– Carl
Aug 1 at 2:21
1
1
And of course, if every point of the sphere is a vertex, then you use axiom of choice/ cardinality arguments to shift some infinite sequence of points so that some point is no longer in the image.
– Carl
Aug 1 at 2:22
And of course, if every point of the sphere is a vertex, then you use axiom of choice/ cardinality arguments to shift some infinite sequence of points so that some point is no longer in the image.
– Carl
Aug 1 at 2:22
 |Â
show 6 more comments
1 Answer
1
active
oldest
votes
up vote
0
down vote
Regarding the comments on 'topological embedding' vs immersed realization: A 'topological graph' in all standard definitions, even for infinite graphs, defines a one-dimensional space (in the sense of covering dim, ind or Ind). Thus, as a one-dimensional subset of a surface (sphere) it does not contain any open set, by the standard result in dimension theory that the open 2-ball has dimension two and the result that dimension is non-increasing for subsets of separable metric spaces. Thus it misses a point of the sphere, which we may assume to be the north pole. Then stereographic projection is an embedding of the graph into the plane.
The general question also has a positive answer. It suffices to show that even if a combinatorial immersion covers the sphere, it is combinatorially equivalent to one which doesn't. Let $v in V$. If $V$ combinatorially immerses in the sphere we have that $E(v)$ has cardinality of the continuum at most, where $E(v)$ is the set of edges containing $v$ as a coordinate. Thus $E(v)$ can be combinatorially immersed in the Cantor Fan. If $G$ is combinatorially immersed in the sphere, then consider the sphere with a closed disc removed. This is homeomorphic to the sphere punctured by $v$. Then we can just draw in the Cantor Fan in this excised neighborhood connecting as needed and obtain that in at least a neighborhood of one point of $G$ we get that the combinatorially equivalent image of the immersion is at most one-dimensional. There is a minor issue about winding toward a circle vs. a point, but all rays converging onto $v$ will have to have the same winding and can be 'unscrewed' simultaneously. I will leave the details for that bit. The result follows.
Note however that this does not necessarily give you a continuous map of the ends of the Cantor Fan onto the boundary circle of the excised neighborhood. In fact it will be impossible to get a continuous function in some cases, since continuous maps from the Cantor set onto the circle are necessarily at least $2$-to-$1$. So you will have to do your immersion in the fan in a potentially complicated and delicate way.
Edit one more time: Actually, I worry about using the Cantor Fan, for pedagogic reasons. Let us instead use a disc with a half-open crescent removed, one corner at $v$ and one at the boundary. Then we get a foliation that bijects with the boundary circle of the excised neighborhood in a trivial way. I am leaving up my first bad idea to give a new question: What conditions ensure that there always exist a vertex where the Cantor Fan is sufficient and can be immersed, as above, but continuously? I wonder, because if not you will have vertices all of whose neighborhoods of arcs are very fat, and compactness might smush some of these 'neighborhoods' together in ways that force some points to behave trivially. Though you might think about a Wada Basin scenario where the smushing isn't helpful. If you allow multigraphs, then a foliation by great circles through two antipodes does not allow this construction.
answered Aug 1 at 1:58
John Samples
989415
This is not the question. The OP is asking whether this is true for infinite graphs.
– Cheerful Parsnip
Aug 1 at 2:10
I expanded the answer.
– John Samples
Aug 1 at 3:00
Upon further reflection, my method can show more. If we do this same 'peeling' procedure along a non-trivial edge, rather than a point, we again obtain a combinatorially equivalent immersion. We can take a nested sequence of finite open covers and do the peeling in a controlled way in each neighborhood. Doing so will eventually produce a combinatorially equivalent immersion whose image is one-dimensional. This result is presumably in the literature somewhere, ask Diestel.
– John Samples
Aug 1 at 6:57
Huh. Apparently my absolutely correct solution was so gobsmackingly beautiful that somebody accidentally gave it a -1 . . . salty
– John Samples
Aug 1 at 9:58
First of all, in most of the literature a planar graph is only defined for finite graphs (at least in Diestel, Bollobas and even in topological graph theory by Tucker and Gross). I was wondering because in my lecture notes we did not have that restriction. Also, to be honest, I am not quite sure if I understand what you've written. Maybe I just have to think about it a little bit more. Nevertheless, thank you anyways!
– TilBe
Aug 1 at 10:13
 |Â
show 12 more comments
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
Regarding the comments on 'topological embedding' vs immersed realization: A 'topological graph' in all standard definitions, even for infinite graphs, defines a one-dimensional space (in the sense of covering dim, ind or Ind). Thus, as a one-dimensional subset of a surface (sphere) it does not contain any open set, by the standard result in dimension theory that the open 2-ball has dimension two and the result that dimension is non-increasing for subsets of separable metric spaces. Thus it misses a point of the sphere, which we may assume to be the north pole. Then stereographic projection is an embedding of the graph into the plane.
The general question also has a positive answer. It suffices to show that even if a combinatorial immersion covers the sphere, it is combinatorially equivalent to one which doesn't. Let $v in V$. If $V$ combinatorially immerses in the sphere we have that $E(v)$ has cardinality of the continuum at most, where $E(v)$ is the set of edges containing $v$ as a coordinate. Thus $E(v)$ can be combinatorially immersed in the Cantor Fan. If $G$ is combinatorially immersed in the sphere, then consider the sphere with a closed disc removed. This is homeomorphic to the sphere punctured by $v$. Then we can just draw in the Cantor Fan in this excised neighborhood connecting as needed and obtain that in at least a neighborhood of one point of $G$ we get that the combinatorially equivalent image of the immersion is at most one-dimensional. There is a minor issue about winding toward a circle vs. a point, but all rays converging onto $v$ will have to have the same winding and can be 'unscrewed' simultaneously. I will leave the details for that bit. The result follows.
Note however that this does not necessarily give you a continuous map of the ends of the Cantor Fan onto the boundary circle of the excised neighborhood. In fact it will be impossible to get a continuous function in some cases, since continuous maps from the Cantor set onto the circle are necessarily at least $2$-to-$1$. So you will have to do your immersion in the fan in a potentially complicated and delicate way.
Edit one more time: Actually, I worry about using the Cantor Fan, for pedagogic reasons. Let us instead use a disc with a half-open crescent removed, one corner at $v$ and one at the boundary. Then we get a foliation that bijects with the boundary circle of the excised neighborhood in a trivial way. I am leaving up my first bad idea to give a new question: What conditions ensure that there always exist a vertex where the Cantor Fan is sufficient and can be immersed, as above, but continuously? I wonder, because if not you will have vertices all of whose neighborhoods of arcs are very fat, and compactness might smush some of these 'neighborhoods' together in ways that force some points to behave trivially. Though you might think about a Wada Basin scenario where the smushing isn't helpful. If you allow multigraphs, then a foliation by great circles through two antipodes does not allow this construction.
answered Aug 1 at 1:58
John Samples
989415
This is not the question. The OP is asking whether this is true for infinite graphs.
– Cheerful Parsnip
Aug 1 at 2:10
I expanded the answer.
– John Samples
Aug 1 at 3:00
Upon further reflection, my method can show more. If we do this same 'peeling' procedure along a non-trivial edge, rather than a point, we again obtain a combinatorially equivalent immersion. We can take a nested sequence of finite open covers and do the peeling in a controlled way in each neighborhood. Doing so will eventually produce a combinatorially equivalent immersion whose image is one-dimensional. This result is presumably in the literature somewhere, ask Diestel.
– John Samples
Aug 1 at 6:57
Huh. Apparently my absolutely correct solution was so gobsmackingly beautiful that somebody accidentally gave it a -1 . . . salty
– John Samples
Aug 1 at 9:58
First of all, in most of the literature a planar graph is only defined for finite graphs (at least in Diestel, Bollobas and even in topological graph theory by Tucker and Gross). I was wondering because in my lecture notes we did not have that restriction. Also, to be honest, I am not quite sure if I understand what you've written. Maybe I just have to think about it a little bit more. Nevertheless, thank you anyways!
– TilBe
Aug 1 at 10:13
 |Â
show 12 more comments
up vote
0
down vote
Regarding the comments on 'topological embedding' vs immersed realization: A 'topological graph' in all standard definitions, even for infinite graphs, defines a one-dimensional space (in the sense of covering dim, ind or Ind). Thus, as a one-dimensional subset of a surface (sphere) it does not contain any open set, by the standard result in dimension theory that the open 2-ball has dimension two and the result that dimension is non-increasing for subsets of separable metric spaces. Thus it misses a point of the sphere, which we may assume to be the north pole. Then stereographic projection is an embedding of the graph into the plane.
The general question also has a positive answer. It suffices to show that even if a combinatorial immersion covers the sphere, it is combinatorially equivalent to one which doesn't. Let $v in V$. If $V$ combinatorially immerses in the sphere we have that $E(v)$ has cardinality of the continuum at most, where $E(v)$ is the set of edges containing $v$ as a coordinate. Thus $E(v)$ can be combinatorially immersed in the Cantor Fan. If $G$ is combinatorially immersed in the sphere, then consider the sphere with a closed disc removed. This is homeomorphic to the sphere punctured by $v$. Then we can just draw in the Cantor Fan in this excised neighborhood connecting as needed and obtain that in at least a neighborhood of one point of $G$ we get that the combinatorially equivalent image of the immersion is at most one-dimensional. There is a minor issue about winding toward a circle vs. a point, but all rays converging onto $v$ will have to have the same winding and can be 'unscrewed' simultaneously. I will leave the details for that bit. The result follows.
Note however that this does not necessarily give you a continuous map of the ends of the Cantor Fan onto the boundary circle of the excised neighborhood. In fact it will be impossible to get a continuous function in some cases, since continuous maps from the Cantor set onto the circle are necessarily at least $2$-to-$1$. So you will have to do your immersion in the fan in a potentially complicated and delicate way.
Edit one more time: Actually, I worry about using the Cantor Fan, for pedagogic reasons. Let us instead use a disc with a half-open crescent removed, one corner at $v$ and one at the boundary. Then we get a foliation that bijects with the boundary circle of the excised neighborhood in a trivial way. I am leaving up my first bad idea to give a new question: What conditions ensure that there always exist a vertex where the Cantor Fan is sufficient and can be immersed, as above, but continuously? I wonder, because if not you will have vertices all of whose neighborhoods of arcs are very fat, and compactness might smush some of these 'neighborhoods' together in ways that force some points to behave trivially. Though you might think about a Wada Basin scenario where the smushing isn't helpful. If you allow multigraphs, then a foliation by great circles through two antipodes does not allow this construction.
answered Aug 1 at 1:58
John Samples
989415
This is not the question. The OP is asking whether this is true for infinite graphs.
– Cheerful Parsnip
Aug 1 at 2:10
I expanded the answer.
– John Samples
Aug 1 at 3:00
Upon further reflection, my method can show more. If we do this same 'peeling' procedure along a non-trivial edge, rather than a point, we again obtain a combinatorially equivalent immersion. We can take a nested sequence of finite open covers and do the peeling in a controlled way in each neighborhood. Doing so will eventually produce a combinatorially equivalent immersion whose image is one-dimensional. This result is presumably in the literature somewhere, ask Diestel.
– John Samples
Aug 1 at 6:57
Huh. Apparently my absolutely correct solution was so gobsmackingly beautiful that somebody accidentally gave it a -1 . . . salty
– John Samples
Aug 1 at 9:58
First of all, in most of the literature a planar graph is only defined for finite graphs (at least in Diestel, Bollobas and even in topological graph theory by Tucker and Gross). I was wondering because in my lecture notes we did not have that restriction. Also, to be honest, I am not quite sure if I understand what you've written. Maybe I just have to think about it a little bit more. Nevertheless, thank you anyways!
– TilBe
Aug 1 at 10:13
 |Â
show 12 more comments
up vote
0
down vote
up vote
0
down vote
Regarding the comments on 'topological embedding' vs immersed realization: A 'topological graph' in all standard definitions, even for infinite graphs, defines a one-dimensional space (in the sense of covering dim, ind or Ind). Thus, as a one-dimensional subset of a surface (sphere) it does not contain any open set, by the standard result in dimension theory that the open 2-ball has dimension two and the result that dimension is non-increasing for subsets of separable metric spaces. Thus it misses a point of the sphere, which we may assume to be the north pole. Then stereographic projection is an embedding of the graph into the plane.
The general question also has a positive answer. It suffices to show that even if a combinatorial immersion covers the sphere, it is combinatorially equivalent to one which doesn't. Let $v in V$. If $V$ combinatorially immerses in the sphere we have that $E(v)$ has cardinality of the continuum at most, where $E(v)$ is the set of edges containing $v$ as a coordinate. Thus $E(v)$ can be combinatorially immersed in the Cantor Fan. If $G$ is combinatorially immersed in the sphere, then consider the sphere with a closed disc removed. This is homeomorphic to the sphere punctured by $v$. Then we can just draw in the Cantor Fan in this excised neighborhood connecting as needed and obtain that in at least a neighborhood of one point of $G$ we get that the combinatorially equivalent image of the immersion is at most one-dimensional. There is a minor issue about winding toward a circle vs. a point, but all rays converging onto $v$ will have to have the same winding and can be 'unscrewed' simultaneously. I will leave the details for that bit. The result follows.
Note however that this does not necessarily give you a continuous map of the ends of the Cantor Fan onto the boundary circle of the excised neighborhood. In fact it will be impossible to get a continuous function in some cases, since continuous maps from the Cantor set onto the circle are necessarily at least $2$-to-$1$. So you will have to do your immersion in the fan in a potentially complicated and delicate way.
Edit one more time: Actually, I worry about using the Cantor Fan, for pedagogic reasons. Let us instead use a disc with a half-open crescent removed, one corner at $v$ and one at the boundary. Then we get a foliation that bijects with the boundary circle of the excised neighborhood in a trivial way. I am leaving up my first bad idea to give a new question: What conditions ensure that there always exist a vertex where the Cantor Fan is sufficient and can be immersed, as above, but continuously? I wonder, because if not you will have vertices all of whose neighborhoods of arcs are very fat, and compactness might smush some of these 'neighborhoods' together in ways that force some points to behave trivially. Though you might think about a Wada Basin scenario where the smushing isn't helpful. If you allow multigraphs, then a foliation by great circles through two antipodes does not allow this construction.
answered Aug 1 at 1:58
John Samples
989415
Regarding the comments on 'topological embedding' vs immersed realization: A 'topological graph' in all standard definitions, even for infinite graphs, defines a one-dimensional space (in the sense of covering dim, ind or Ind). Thus, as a one-dimensional subset of a surface (sphere) it does not contain any open set, by the standard result in dimension theory that the open 2-ball has dimension two and the result that dimension is non-increasing for subsets of separable metric spaces. Thus it misses a point of the sphere, which we may assume to be the north pole. Then stereographic projection is an embedding of the graph into the plane.
The general question also has a positive answer. It suffices to show that even if a combinatorial immersion covers the sphere, it is combinatorially equivalent to one which doesn't. Let $v in V$. If $V$ combinatorially immerses in the sphere we have that $E(v)$ has cardinality of the continuum at most, where $E(v)$ is the set of edges containing $v$ as a coordinate. Thus $E(v)$ can be combinatorially immersed in the Cantor Fan. If $G$ is combinatorially immersed in the sphere, then consider the sphere with a closed disc removed. This is homeomorphic to the sphere punctured by $v$. Then we can just draw in the Cantor Fan in this excised neighborhood connecting as needed and obtain that in at least a neighborhood of one point of $G$ we get that the combinatorially equivalent image of the immersion is at most one-dimensional. There is a minor issue about winding toward a circle vs. a point, but all rays converging onto $v$ will have to have the same winding and can be 'unscrewed' simultaneously. I will leave the details for that bit. The result follows.
Note however that this does not necessarily give you a continuous map of the ends of the Cantor Fan onto the boundary circle of the excised neighborhood. In fact it will be impossible to get a continuous function in some cases, since continuous maps from the Cantor set onto the circle are necessarily at least $2$-to-$1$. So you will have to do your immersion in the fan in a potentially complicated and delicate way.
Edit one more time: Actually, I worry about using the Cantor Fan, for pedagogic reasons. Let us instead use a disc with a half-open crescent removed, one corner at $v$ and one at the boundary. Then we get a foliation that bijects with the boundary circle of the excised neighborhood in a trivial way. I am leaving up my first bad idea to give a new question: What conditions ensure that there always exist a vertex where the Cantor Fan is sufficient and can be immersed, as above, but continuously? I wonder, because if not you will have vertices all of whose neighborhoods of arcs are very fat, and compactness might smush some of these 'neighborhoods' together in ways that force some points to behave trivially. Though you might think about a Wada Basin scenario where the smushing isn't helpful. If you allow multigraphs, then a foliation by great circles through two antipodes does not allow this construction.
answered Aug 1 at 1:58
John Samples
989415
edited Aug 1 at 19:51
answered Aug 1 at 1:58
John Samples
989415
answered Aug 1 at 1:58
John Samples
989415
answered Aug 1 at 1:58
John Samples
989415
989415
This is not the question. The OP is asking whether this is true for infinite graphs.
– Cheerful Parsnip
Aug 1 at 2:10
I expanded the answer.
– John Samples
Aug 1 at 3:00
Upon further reflection, my method can show more. If we do this same 'peeling' procedure along a non-trivial edge, rather than a point, we again obtain a combinatorially equivalent immersion. We can take a nested sequence of finite open covers and do the peeling in a controlled way in each neighborhood. Doing so will eventually produce a combinatorially equivalent immersion whose image is one-dimensional. This result is presumably in the literature somewhere, ask Diestel.
– John Samples
Aug 1 at 6:57
Huh. Apparently my absolutely correct solution was so gobsmackingly beautiful that somebody accidentally gave it a -1 . . . salty
– John Samples
Aug 1 at 9:58
First of all, in most of the literature a planar graph is only defined for finite graphs (at least in Diestel, Bollobas and even in topological graph theory by Tucker and Gross). I was wondering because in my lecture notes we did not have that restriction. Also, to be honest, I am not quite sure if I understand what you've written. Maybe I just have to think about it a little bit more. Nevertheless, thank you anyways!
– TilBe
Aug 1 at 10:13
 |Â
show 12 more comments
This is not the question. The OP is asking whether this is true for infinite graphs.
– Cheerful Parsnip
Aug 1 at 2:10
I expanded the answer.
– John Samples
Aug 1 at 3:00
Upon further reflection, my method can show more. If we do this same 'peeling' procedure along a non-trivial edge, rather than a point, we again obtain a combinatorially equivalent immersion. We can take a nested sequence of finite open covers and do the peeling in a controlled way in each neighborhood. Doing so will eventually produce a combinatorially equivalent immersion whose image is one-dimensional. This result is presumably in the literature somewhere, ask Diestel.
– John Samples
Aug 1 at 6:57
Huh. Apparently my absolutely correct solution was so gobsmackingly beautiful that somebody accidentally gave it a -1 . . . salty
– John Samples
Aug 1 at 9:58
First of all, in most of the literature a planar graph is only defined for finite graphs (at least in Diestel, Bollobas and even in topological graph theory by Tucker and Gross). I was wondering because in my lecture notes we did not have that restriction. Also, to be honest, I am not quite sure if I understand what you've written. Maybe I just have to think about it a little bit more. Nevertheless, thank you anyways!
– TilBe
Aug 1 at 10:13
This is not the question. The OP is asking whether this is true for infinite graphs.
– Cheerful Parsnip
Aug 1 at 2:10
This is not the question. The OP is asking whether this is true for infinite graphs.
– Cheerful Parsnip
Aug 1 at 2:10
I expanded the answer.
– John Samples
Aug 1 at 3:00
I expanded the answer.
– John Samples
Aug 1 at 3:00
Upon further reflection, my method can show more. If we do this same 'peeling' procedure along a non-trivial edge, rather than a point, we again obtain a combinatorially equivalent immersion. We can take a nested sequence of finite open covers and do the peeling in a controlled way in each neighborhood. Doing so will eventually produce a combinatorially equivalent immersion whose image is one-dimensional. This result is presumably in the literature somewhere, ask Diestel.
– John Samples
Aug 1 at 6:57
Upon further reflection, my method can show more. If we do this same 'peeling' procedure along a non-trivial edge, rather than a point, we again obtain a combinatorially equivalent immersion. We can take a nested sequence of finite open covers and do the peeling in a controlled way in each neighborhood. Doing so will eventually produce a combinatorially equivalent immersion whose image is one-dimensional. This result is presumably in the literature somewhere, ask Diestel.
– John Samples
Aug 1 at 6:57
Huh. Apparently my absolutely correct solution was so gobsmackingly beautiful that somebody accidentally gave it a -1 . . . salty
– John Samples
Aug 1 at 9:58
Huh. Apparently my absolutely correct solution was so gobsmackingly beautiful that somebody accidentally gave it a -1 . . . salty
– John Samples
Aug 1 at 9:58
First of all, in most of the literature a planar graph is only defined for finite graphs (at least in Diestel, Bollobas and even in topological graph theory by Tucker and Gross). I was wondering because in my lecture notes we did not have that restriction. Also, to be honest, I am not quite sure if I understand what you've written. Maybe I just have to think about it a little bit more. Nevertheless, thank you anyways!
– TilBe
Aug 1 at 10:13
First of all, in most of the literature a planar graph is only defined for finite graphs (at least in Diestel, Bollobas and even in topological graph theory by Tucker and Gross). I was wondering because in my lecture notes we did not have that restriction. Also, to be honest, I am not quite sure if I understand what you've written. Maybe I just have to think about it a little bit more. Nevertheless, thank you anyways!
– TilBe
Aug 1 at 10:13
 |Â
show 12 more comments
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2868165%2finfinite-graph-is-planar-iff-it-can-be-embedded-in-sphere%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
1
Sure...you could say that there's an edge from $P$ to $Q$ exactly when they're antipodal, for instance. The usual definition of a graph embedding seems to take into account a kind of topology on the geometric realization of the graph, and that topology doesn't seem to be related (in the case of a graph with all points of $S^2$ as vertices, and no edges) to the topology of the underlying space $S^2$. So using $S^2$ seems like a red herring --- any uncountable set would work equally well.
– John Hughes
Jul 31 at 15:47
2
Henning Makholm's answer to this related question -- math.stackexchange.com/questions/712013/… -- seems very relevant.
– John Hughes
Jul 31 at 15:54
1
Your definition of "embedding" is not what I would consider to be the normal definition of an embedding for an infinite graph. Any graph naturally gives rise to a topological space (just the quotient space obtained by gluing together all its vertices and edges). Your definition is equivalent to a continuous injection from this topological space, rather than a topological embedding.
– Eric Wofsey
Jul 31 at 18:44
1
Assuming you have some awful "embedding" (as Eric says, not really an embedding in the normal sense" where vertices are dense and every point is in the image, you can still get it to be planar. For example, take stereographic projection such that some point lying in an edge is sent to $infty$. Then map the plane by homeomorphism to a smaller simply connected subset of the plane (like a disk). You can now connect the cut edge back up in the complement of that disk to get a planar "embedding"
– Carl
Aug 1 at 2:21
1
And of course, if every point of the sphere is a vertex, then you use axiom of choice/ cardinality arguments to shift some infinite sequence of points so that some point is no longer in the image.
– Carl
Aug 1 at 2:22