How to find the Euler characteristic of a cellularly embedded graph, given only the vertices and edges?
$begingroup$
Suppose that we are given a finite connected graph, i.e. the finite vertex set $V$ and a finite edge set $Esubseteq P(V)$.
Is there an algorithm to find the Euler characteristic of any cellular embedding of our graph?
Recently I learned that it is not easy to find the "faces" if we are only given the vertex set and the edge set. We need to find an embedding into a compact connected surface in a such a way that the complement of the image of the graph is homeomorphic to a disjoint union of open discs (this type of embedding is called cellular, sometimes people also call it just a "map". The connected component of the complement of the image of graph gives us the faces). I am curious how one could find the Euler characteristic of our surface and therefore our surface (up to homeomorphism).
I suppose that after this edit it should be obvious to anybody, why this is NOT a duplicate.
graph-theory algorithms
asked Dec 15 '18 at 21:24
Severin SchravenSeverin Schraven
6,3481934
$endgroup$
|
show 3 more comments
$begingroup$
Suppose that we are given a finite connected graph, i.e. the finite vertex set $V$ and a finite edge set $Esubseteq P(V)$.
Is there an algorithm to find the Euler characteristic of any cellular embedding of our graph?
Recently I learned that it is not easy to find the "faces" if we are only given the vertex set and the edge set. We need to find an embedding into a compact connected surface in a such a way that the complement of the image of the graph is homeomorphic to a disjoint union of open discs (this type of embedding is called cellular, sometimes people also call it just a "map". The connected component of the complement of the image of graph gives us the faces). I am curious how one could find the Euler characteristic of our surface and therefore our surface (up to homeomorphism).
I suppose that after this edit it should be obvious to anybody, why this is NOT a duplicate.
graph-theory algorithms
asked Dec 15 '18 at 21:24
Severin SchravenSeverin Schraven
6,3481934
$endgroup$
1
$begingroup$
Possible duplicate of Euler characteristics for planar vs. non-planar graphs
$endgroup$
– user10354138
Dec 15 '18 at 21:58
$begingroup$
@user10354138 No, it's not.
$endgroup$
– Misha Lavrov
Dec 15 '18 at 22:00
1
$begingroup$
@user10354138 If you want to think of the graph as its own topological space, then sure, but it is clear from the question that we're thinking of embedding the graph into a 2D surface.
$endgroup$
– Misha Lavrov
Dec 15 '18 at 22:04
1
$begingroup$
@SeverinSchraven The close vote will go away eventually on its own (I think they decay at a rate of one per day or so). I suggest not worrying about it.
$endgroup$
– Misha Lavrov
Dec 15 '18 at 22:54
1
$begingroup$
What is the Euler characteristic of a graph?
$endgroup$
– bof
Dec 15 '18 at 23:58
|
show 3 more comments
$begingroup$
Suppose that we are given a finite connected graph, i.e. the finite vertex set $V$ and a finite edge set $Esubseteq P(V)$.
Is there an algorithm to find the Euler characteristic of any cellular embedding of our graph?
Recently I learned that it is not easy to find the "faces" if we are only given the vertex set and the edge set. We need to find an embedding into a compact connected surface in a such a way that the complement of the image of the graph is homeomorphic to a disjoint union of open discs (this type of embedding is called cellular, sometimes people also call it just a "map". The connected component of the complement of the image of graph gives us the faces). I am curious how one could find the Euler characteristic of our surface and therefore our surface (up to homeomorphism).
I suppose that after this edit it should be obvious to anybody, why this is NOT a duplicate.
graph-theory algorithms
asked Dec 15 '18 at 21:24
Severin SchravenSeverin Schraven
6,3481934
$endgroup$
Suppose that we are given a finite connected graph, i.e. the finite vertex set $V$ and a finite edge set $Esubseteq P(V)$.
Is there an algorithm to find the Euler characteristic of any cellular embedding of our graph?
Recently I learned that it is not easy to find the "faces" if we are only given the vertex set and the edge set. We need to find an embedding into a compact connected surface in a such a way that the complement of the image of the graph is homeomorphic to a disjoint union of open discs (this type of embedding is called cellular, sometimes people also call it just a "map". The connected component of the complement of the image of graph gives us the faces). I am curious how one could find the Euler characteristic of our surface and therefore our surface (up to homeomorphism).
I suppose that after this edit it should be obvious to anybody, why this is NOT a duplicate.
graph-theory algorithms
graph-theory algorithms
asked Dec 15 '18 at 21:24
Severin SchravenSeverin Schraven
6,3481934
asked Dec 15 '18 at 21:24
Severin SchravenSeverin Schraven
6,3481934
edited Dec 16 '18 at 10:18
Severin Schraven
asked Dec 15 '18 at 21:24
Severin SchravenSeverin Schraven
6,3481934
asked Dec 15 '18 at 21:24
Severin SchravenSeverin Schraven
6,3481934
asked Dec 15 '18 at 21:24
Severin SchravenSeverin Schraven
6,3481934
6,3481934
1
$begingroup$
Possible duplicate of Euler characteristics for planar vs. non-planar graphs
$endgroup$
– user10354138
Dec 15 '18 at 21:58
$begingroup$
@user10354138 No, it's not.
$endgroup$
– Misha Lavrov
Dec 15 '18 at 22:00
1
$begingroup$
@user10354138 If you want to think of the graph as its own topological space, then sure, but it is clear from the question that we're thinking of embedding the graph into a 2D surface.
$endgroup$
– Misha Lavrov
Dec 15 '18 at 22:04
1
$begingroup$
@SeverinSchraven The close vote will go away eventually on its own (I think they decay at a rate of one per day or so). I suggest not worrying about it.
$endgroup$
– Misha Lavrov
Dec 15 '18 at 22:54
1
$begingroup$
What is the Euler characteristic of a graph?
$endgroup$
– bof
Dec 15 '18 at 23:58
|
show 3 more comments
1
$begingroup$
Possible duplicate of Euler characteristics for planar vs. non-planar graphs
$endgroup$
– user10354138
Dec 15 '18 at 21:58
$begingroup$
@user10354138 No, it's not.
$endgroup$
– Misha Lavrov
Dec 15 '18 at 22:00
1
$begingroup$
@user10354138 If you want to think of the graph as its own topological space, then sure, but it is clear from the question that we're thinking of embedding the graph into a 2D surface.
$endgroup$
– Misha Lavrov
Dec 15 '18 at 22:04
1
$begingroup$
@SeverinSchraven The close vote will go away eventually on its own (I think they decay at a rate of one per day or so). I suggest not worrying about it.
$endgroup$
– Misha Lavrov
Dec 15 '18 at 22:54
1
$begingroup$
What is the Euler characteristic of a graph?
$endgroup$
– bof
Dec 15 '18 at 23:58
1
1
$begingroup$
Possible duplicate of Euler characteristics for planar vs. non-planar graphs
$endgroup$
– user10354138
Dec 15 '18 at 21:58
$begingroup$
Possible duplicate of Euler characteristics for planar vs. non-planar graphs
$endgroup$
– user10354138
Dec 15 '18 at 21:58
$begingroup$
@user10354138 No, it's not.
$endgroup$
– Misha Lavrov
Dec 15 '18 at 22:00
$begingroup$
@user10354138 No, it's not.
$endgroup$
– Misha Lavrov
Dec 15 '18 at 22:00
1
1
$begingroup$
@user10354138 If you want to think of the graph as its own topological space, then sure, but it is clear from the question that we're thinking of embedding the graph into a 2D surface.
$endgroup$
– Misha Lavrov
Dec 15 '18 at 22:04
$begingroup$
@user10354138 If you want to think of the graph as its own topological space, then sure, but it is clear from the question that we're thinking of embedding the graph into a 2D surface.
$endgroup$
– Misha Lavrov
Dec 15 '18 at 22:04
1
1
$begingroup$
@SeverinSchraven The close vote will go away eventually on its own (I think they decay at a rate of one per day or so). I suggest not worrying about it.
$endgroup$
– Misha Lavrov
Dec 15 '18 at 22:54
$begingroup$
@SeverinSchraven The close vote will go away eventually on its own (I think they decay at a rate of one per day or so). I suggest not worrying about it.
$endgroup$
– Misha Lavrov
Dec 15 '18 at 22:54
1
1
$begingroup$
What is the Euler characteristic of a graph?
$endgroup$
– bof
Dec 15 '18 at 23:58
$begingroup$
What is the Euler characteristic of a graph?
$endgroup$
– bof
Dec 15 '18 at 23:58
|
show 3 more comments
1 Answer
1
active
oldest
votes
$begingroup$
Rather than speaking of the Euler characteristic of a graph, we traditionally speak of the genus of a graph, which is the least genus of a surface into which it can be embedded...
...but there is no way to find this number that improves substantially on finding all embeddings of the graph.
This CS StackExchange answer outlines a method. The basic idea is that the global structure of the embedding is determined by some local decisions: for each vertex, you should determine the cyclic order of the edges out of that vertex.
Not all choices made at the different vertices are compatible, so we work out the ones that are, and now we can work out the faces of this embedding and determine the genus (or, if you prefer, the Euler characteristic). If we do this for all possible ways to choose the cyclic orders, we can get a bunch of embeddings, and then we can choose the best one.
There are better algorithms, and there are ways to speed up this algorithm so we don't have to check very possibility, but there's no fast algorithm. See Wikipedia for some citations.
answered Dec 15 '18 at 21:58
Misha LavrovMisha Lavrov
47.4k657107
$endgroup$
$begingroup$
That is pretty surprising. Thank you for the nice answer and the comment to make clear why this no duplicate.
$endgroup$
– Severin Schraven
Dec 15 '18 at 22:40
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3041981%2fhow-to-find-the-euler-characteristic-of-a-cellularly-embedded-graph-given-only%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Rather than speaking of the Euler characteristic of a graph, we traditionally speak of the genus of a graph, which is the least genus of a surface into which it can be embedded...
...but there is no way to find this number that improves substantially on finding all embeddings of the graph.
This CS StackExchange answer outlines a method. The basic idea is that the global structure of the embedding is determined by some local decisions: for each vertex, you should determine the cyclic order of the edges out of that vertex.
Not all choices made at the different vertices are compatible, so we work out the ones that are, and now we can work out the faces of this embedding and determine the genus (or, if you prefer, the Euler characteristic). If we do this for all possible ways to choose the cyclic orders, we can get a bunch of embeddings, and then we can choose the best one.
There are better algorithms, and there are ways to speed up this algorithm so we don't have to check very possibility, but there's no fast algorithm. See Wikipedia for some citations.
answered Dec 15 '18 at 21:58
Misha LavrovMisha Lavrov
47.4k657107
$endgroup$
$begingroup$
That is pretty surprising. Thank you for the nice answer and the comment to make clear why this no duplicate.
$endgroup$
– Severin Schraven
Dec 15 '18 at 22:40
add a comment |
$begingroup$
Rather than speaking of the Euler characteristic of a graph, we traditionally speak of the genus of a graph, which is the least genus of a surface into which it can be embedded...
...but there is no way to find this number that improves substantially on finding all embeddings of the graph.
This CS StackExchange answer outlines a method. The basic idea is that the global structure of the embedding is determined by some local decisions: for each vertex, you should determine the cyclic order of the edges out of that vertex.
Not all choices made at the different vertices are compatible, so we work out the ones that are, and now we can work out the faces of this embedding and determine the genus (or, if you prefer, the Euler characteristic). If we do this for all possible ways to choose the cyclic orders, we can get a bunch of embeddings, and then we can choose the best one.
There are better algorithms, and there are ways to speed up this algorithm so we don't have to check very possibility, but there's no fast algorithm. See Wikipedia for some citations.
answered Dec 15 '18 at 21:58
Misha LavrovMisha Lavrov
47.4k657107
$endgroup$
$begingroup$
That is pretty surprising. Thank you for the nice answer and the comment to make clear why this no duplicate.
$endgroup$
– Severin Schraven
Dec 15 '18 at 22:40
add a comment |
$begingroup$
Rather than speaking of the Euler characteristic of a graph, we traditionally speak of the genus of a graph, which is the least genus of a surface into which it can be embedded...
...but there is no way to find this number that improves substantially on finding all embeddings of the graph.
This CS StackExchange answer outlines a method. The basic idea is that the global structure of the embedding is determined by some local decisions: for each vertex, you should determine the cyclic order of the edges out of that vertex.
Not all choices made at the different vertices are compatible, so we work out the ones that are, and now we can work out the faces of this embedding and determine the genus (or, if you prefer, the Euler characteristic). If we do this for all possible ways to choose the cyclic orders, we can get a bunch of embeddings, and then we can choose the best one.
There are better algorithms, and there are ways to speed up this algorithm so we don't have to check very possibility, but there's no fast algorithm. See Wikipedia for some citations.
answered Dec 15 '18 at 21:58
Misha LavrovMisha Lavrov
47.4k657107
$endgroup$
Rather than speaking of the Euler characteristic of a graph, we traditionally speak of the genus of a graph, which is the least genus of a surface into which it can be embedded...
...but there is no way to find this number that improves substantially on finding all embeddings of the graph.
This CS StackExchange answer outlines a method. The basic idea is that the global structure of the embedding is determined by some local decisions: for each vertex, you should determine the cyclic order of the edges out of that vertex.
Not all choices made at the different vertices are compatible, so we work out the ones that are, and now we can work out the faces of this embedding and determine the genus (or, if you prefer, the Euler characteristic). If we do this for all possible ways to choose the cyclic orders, we can get a bunch of embeddings, and then we can choose the best one.
There are better algorithms, and there are ways to speed up this algorithm so we don't have to check very possibility, but there's no fast algorithm. See Wikipedia for some citations.
answered Dec 15 '18 at 21:58
Misha LavrovMisha Lavrov
47.4k657107
answered Dec 15 '18 at 21:58
Misha LavrovMisha Lavrov
47.4k657107
answered Dec 15 '18 at 21:58
Misha LavrovMisha Lavrov
47.4k657107
answered Dec 15 '18 at 21:58
Misha LavrovMisha Lavrov
47.4k657107
47.4k657107
$begingroup$
That is pretty surprising. Thank you for the nice answer and the comment to make clear why this no duplicate.
$endgroup$
– Severin Schraven
Dec 15 '18 at 22:40
add a comment |
$begingroup$
That is pretty surprising. Thank you for the nice answer and the comment to make clear why this no duplicate.
$endgroup$
– Severin Schraven
Dec 15 '18 at 22:40
$begingroup$
That is pretty surprising. Thank you for the nice answer and the comment to make clear why this no duplicate.
$endgroup$
– Severin Schraven
Dec 15 '18 at 22:40
$begingroup$
That is pretty surprising. Thank you for the nice answer and the comment to make clear why this no duplicate.
$endgroup$
– Severin Schraven
Dec 15 '18 at 22:40
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3041981%2fhow-to-find-the-euler-characteristic-of-a-cellularly-embedded-graph-given-only%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
Possible duplicate of Euler characteristics for planar vs. non-planar graphs
$endgroup$
– user10354138
Dec 15 '18 at 21:58
$begingroup$
@user10354138 No, it's not.
$endgroup$
– Misha Lavrov
Dec 15 '18 at 22:00
1
$begingroup$
@user10354138 If you want to think of the graph as its own topological space, then sure, but it is clear from the question that we're thinking of embedding the graph into a 2D surface.
$endgroup$
– Misha Lavrov
Dec 15 '18 at 22:04
1
$begingroup$
@SeverinSchraven The close vote will go away eventually on its own (I think they decay at a rate of one per day or so). I suggest not worrying about it.
$endgroup$
– Misha Lavrov
Dec 15 '18 at 22:54
1
$begingroup$
What is the Euler characteristic of a graph?
$endgroup$
– bof
Dec 15 '18 at 23:58