Finding coordinates so that no line intersect each other
$begingroup$
This is an exercise I came up with, but can't solve myself.... Here goes:
Say you receive as input a list of N nodes. Each node n is connected to one or more nodes. The input could look something like:
Node A is linked to node B and C
Node B is linked to node A and C
Node C is linked to node A and B
The goal is to find a function that maps each node to a coordinate in a plane in such a way that the straight lines connecting each node do not intersect each other.
The example above is trivial: As long as the nodes are not all on the same axis it will work, but it gets lot harder with more nodes and more links between them. I'm assuming some inputs do not have any valid answer, but I don't see how you can prove it.
geometry
asked Dec 8 '18 at 15:34
MyUsername112358MyUsername112358
1135
$endgroup$
add a comment |
$begingroup$
This is an exercise I came up with, but can't solve myself.... Here goes:
Say you receive as input a list of N nodes. Each node n is connected to one or more nodes. The input could look something like:
Node A is linked to node B and C
Node B is linked to node A and C
Node C is linked to node A and B
The goal is to find a function that maps each node to a coordinate in a plane in such a way that the straight lines connecting each node do not intersect each other.
The example above is trivial: As long as the nodes are not all on the same axis it will work, but it gets lot harder with more nodes and more links between them. I'm assuming some inputs do not have any valid answer, but I don't see how you can prove it.
geometry
asked Dec 8 '18 at 15:34
MyUsername112358MyUsername112358
1135
$endgroup$
2
$begingroup$
This is a question about planar graphs. There are algorithms that detect planarity. Google "planar graph" and you'll get thousands (at least) of hits.
$endgroup$
– saulspatz
Dec 8 '18 at 15:43
$begingroup$
Thanks! I didn't know enough about the problem to know what to google for, but it does look like planar graph is what I'm looking for :)
$endgroup$
– MyUsername112358
Dec 8 '18 at 15:45
$begingroup$
It was my pleasure.
$endgroup$
– saulspatz
Dec 8 '18 at 15:48
$begingroup$
Feel free to answer your own question, summarizing your findings.
$endgroup$
– MvG
Dec 10 '18 at 21:43
add a comment |
$begingroup$
This is an exercise I came up with, but can't solve myself.... Here goes:
Say you receive as input a list of N nodes. Each node n is connected to one or more nodes. The input could look something like:
Node A is linked to node B and C
Node B is linked to node A and C
Node C is linked to node A and B
The goal is to find a function that maps each node to a coordinate in a plane in such a way that the straight lines connecting each node do not intersect each other.
The example above is trivial: As long as the nodes are not all on the same axis it will work, but it gets lot harder with more nodes and more links between them. I'm assuming some inputs do not have any valid answer, but I don't see how you can prove it.
geometry
asked Dec 8 '18 at 15:34
MyUsername112358MyUsername112358
1135
$endgroup$
This is an exercise I came up with, but can't solve myself.... Here goes:
Say you receive as input a list of N nodes. Each node n is connected to one or more nodes. The input could look something like:
Node A is linked to node B and C
Node B is linked to node A and C
Node C is linked to node A and B
The goal is to find a function that maps each node to a coordinate in a plane in such a way that the straight lines connecting each node do not intersect each other.
The example above is trivial: As long as the nodes are not all on the same axis it will work, but it gets lot harder with more nodes and more links between them. I'm assuming some inputs do not have any valid answer, but I don't see how you can prove it.
geometry
geometry
asked Dec 8 '18 at 15:34
MyUsername112358MyUsername112358
1135
asked Dec 8 '18 at 15:34
MyUsername112358MyUsername112358
1135
asked Dec 8 '18 at 15:34
MyUsername112358MyUsername112358
1135
asked Dec 8 '18 at 15:34
MyUsername112358MyUsername112358
1135
asked Dec 8 '18 at 15:34
MyUsername112358MyUsername112358
1135
1135
2
$begingroup$
This is a question about planar graphs. There are algorithms that detect planarity. Google "planar graph" and you'll get thousands (at least) of hits.
$endgroup$
– saulspatz
Dec 8 '18 at 15:43
$begingroup$
Thanks! I didn't know enough about the problem to know what to google for, but it does look like planar graph is what I'm looking for :)
$endgroup$
– MyUsername112358
Dec 8 '18 at 15:45
$begingroup$
It was my pleasure.
$endgroup$
– saulspatz
Dec 8 '18 at 15:48
$begingroup$
Feel free to answer your own question, summarizing your findings.
$endgroup$
– MvG
Dec 10 '18 at 21:43
add a comment |
2
$begingroup$
This is a question about planar graphs. There are algorithms that detect planarity. Google "planar graph" and you'll get thousands (at least) of hits.
$endgroup$
– saulspatz
Dec 8 '18 at 15:43
$begingroup$
Thanks! I didn't know enough about the problem to know what to google for, but it does look like planar graph is what I'm looking for :)
$endgroup$
– MyUsername112358
Dec 8 '18 at 15:45
$begingroup$
It was my pleasure.
$endgroup$
– saulspatz
Dec 8 '18 at 15:48
$begingroup$
Feel free to answer your own question, summarizing your findings.
$endgroup$
– MvG
Dec 10 '18 at 21:43
2
2
$begingroup$
This is a question about planar graphs. There are algorithms that detect planarity. Google "planar graph" and you'll get thousands (at least) of hits.
$endgroup$
– saulspatz
Dec 8 '18 at 15:43
$begingroup$
This is a question about planar graphs. There are algorithms that detect planarity. Google "planar graph" and you'll get thousands (at least) of hits.
$endgroup$
– saulspatz
Dec 8 '18 at 15:43
$begingroup$
Thanks! I didn't know enough about the problem to know what to google for, but it does look like planar graph is what I'm looking for :)
$endgroup$
– MyUsername112358
Dec 8 '18 at 15:45
$begingroup$
Thanks! I didn't know enough about the problem to know what to google for, but it does look like planar graph is what I'm looking for :)
$endgroup$
– MyUsername112358
Dec 8 '18 at 15:45
$begingroup$
It was my pleasure.
$endgroup$
– saulspatz
Dec 8 '18 at 15:48
$begingroup$
It was my pleasure.
$endgroup$
– saulspatz
Dec 8 '18 at 15:48
$begingroup$
Feel free to answer your own question, summarizing your findings.
$endgroup$
– MvG
Dec 10 '18 at 21:43
$begingroup$
Feel free to answer your own question, summarizing your findings.
$endgroup$
– MvG
Dec 10 '18 at 21:43
add a comment |
0
active
oldest
votes
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%2f3031240%2ffinding-coordinates-so-that-no-line-intersect-each-other%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3031240%2ffinding-coordinates-so-that-no-line-intersect-each-other%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
2
$begingroup$
This is a question about planar graphs. There are algorithms that detect planarity. Google "planar graph" and you'll get thousands (at least) of hits.
$endgroup$
– saulspatz
Dec 8 '18 at 15:43
$begingroup$
Thanks! I didn't know enough about the problem to know what to google for, but it does look like planar graph is what I'm looking for :)
$endgroup$
– MyUsername112358
Dec 8 '18 at 15:45
$begingroup$
It was my pleasure.
$endgroup$
– saulspatz
Dec 8 '18 at 15:48
$begingroup$
Feel free to answer your own question, summarizing your findings.
$endgroup$
– MvG
Dec 10 '18 at 21:43