Mixing
Draw a specific graph with a branching.
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
I want to draw the following graph:
- it is a tree
- it can have up to four children nodes
- there should be no edges intersections
The part with which I struggle is the 3. I am not sure how to avoid the intersections.
Whatever distance I will take between sibling nodes eventually an intersection will occur if I will add four children to each node enough times.
Is it possible to accomplish at all?
I am going to draw the graph programmatically.
geometry graph-theory trees
edited Jul 27 at 20:00
Xander Henderson
13.1k83150
asked Jul 27 at 19:49
iloveseven
1011
 |Â
show 1 more comment
up vote
0
down vote
favorite
I want to draw the following graph:
- it is a tree
- it can have up to four children nodes
- there should be no edges intersections
The part with which I struggle is the 3. I am not sure how to avoid the intersections.
Whatever distance I will take between sibling nodes eventually an intersection will occur if I will add four children to each node enough times.
Is it possible to accomplish at all?
I am going to draw the graph programmatically.
geometry graph-theory trees
edited Jul 27 at 20:00
Xander Henderson
13.1k83150
asked Jul 27 at 19:49
iloveseven
1011
2
I do not understand what you mean by "edges intersections" and why you think they are unavoidable. It is well known that a tree is a planar graph and so admits a planar drawing. It sounds like you are wanting to draw a rooted tree where each parent vertex can have up to four children and you want to draw it in a way that avoids crossings. In your image you draw a line between siblings... that should not be done in a tree. The image you link is not a tree at all (it has a cycle).
– JMoravitz
Jul 27 at 19:54
You know how many nodes are potentially on each layer (assuming 4 "children" from each node in the layer above). Just draw any nodes for that layer in their appropriate position along the line and join to their parent.
– Joffan
Jul 27 at 20:04
@JMoravitz, that line is not an edge it is just to show what I mean by distance between siblings. I am sorry for confusion.
– iloveseven
Jul 27 at 20:08
@Joffan, do you mean just start drawing from the bottom given the data (set of nodes and edges) for the graph?
– iloveseven
Jul 27 at 20:09
Or you could just do it from top down... Suppose for instance that we notate vertices as sequences of $A$'s, $B$'s, $C$'s and $D$'s, corresponding to the specific ancestry of the vertex. For example, $AACB$ is the second child of $AAC$ who is the third child of $AA$ who is the first child of $A$. For each generation, just write all $n$'th generational vertices in a line in alphabetical order. No lines will ever cross in such a scenario (though some will become heavily slanted).
– JMoravitz
Jul 27 at 20:29
 |Â
show 1 more comment
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I want to draw the following graph:
- it is a tree
- it can have up to four children nodes
- there should be no edges intersections
The part with which I struggle is the 3. I am not sure how to avoid the intersections.
Whatever distance I will take between sibling nodes eventually an intersection will occur if I will add four children to each node enough times.
Is it possible to accomplish at all?
I am going to draw the graph programmatically.
geometry graph-theory trees
edited Jul 27 at 20:00
Xander Henderson
13.1k83150
asked Jul 27 at 19:49
iloveseven
1011
I want to draw the following graph:
- it is a tree
- it can have up to four children nodes
- there should be no edges intersections
The part with which I struggle is the 3. I am not sure how to avoid the intersections.
Whatever distance I will take between sibling nodes eventually an intersection will occur if I will add four children to each node enough times.
Is it possible to accomplish at all?
I am going to draw the graph programmatically.
geometry graph-theory trees
edited Jul 27 at 20:00
Xander Henderson
13.1k83150
asked Jul 27 at 19:49
iloveseven
1011
edited Jul 27 at 20:00
Xander Henderson
13.1k83150
edited Jul 27 at 20:00
Xander Henderson
13.1k83150
edited Jul 27 at 20:00
Xander Henderson
13.1k83150
13.1k83150
asked Jul 27 at 19:49
iloveseven
1011
asked Jul 27 at 19:49
iloveseven
1011
asked Jul 27 at 19:49
iloveseven
1011
1011
2
I do not understand what you mean by "edges intersections" and why you think they are unavoidable. It is well known that a tree is a planar graph and so admits a planar drawing. It sounds like you are wanting to draw a rooted tree where each parent vertex can have up to four children and you want to draw it in a way that avoids crossings. In your image you draw a line between siblings... that should not be done in a tree. The image you link is not a tree at all (it has a cycle).
– JMoravitz
Jul 27 at 19:54
You know how many nodes are potentially on each layer (assuming 4 "children" from each node in the layer above). Just draw any nodes for that layer in their appropriate position along the line and join to their parent.
– Joffan
Jul 27 at 20:04
@JMoravitz, that line is not an edge it is just to show what I mean by distance between siblings. I am sorry for confusion.
– iloveseven
Jul 27 at 20:08
@Joffan, do you mean just start drawing from the bottom given the data (set of nodes and edges) for the graph?
– iloveseven
Jul 27 at 20:09
Or you could just do it from top down... Suppose for instance that we notate vertices as sequences of $A$'s, $B$'s, $C$'s and $D$'s, corresponding to the specific ancestry of the vertex. For example, $AACB$ is the second child of $AAC$ who is the third child of $AA$ who is the first child of $A$. For each generation, just write all $n$'th generational vertices in a line in alphabetical order. No lines will ever cross in such a scenario (though some will become heavily slanted).
– JMoravitz
Jul 27 at 20:29
 |Â
show 1 more comment
2
I do not understand what you mean by "edges intersections" and why you think they are unavoidable. It is well known that a tree is a planar graph and so admits a planar drawing. It sounds like you are wanting to draw a rooted tree where each parent vertex can have up to four children and you want to draw it in a way that avoids crossings. In your image you draw a line between siblings... that should not be done in a tree. The image you link is not a tree at all (it has a cycle).
– JMoravitz
Jul 27 at 19:54
You know how many nodes are potentially on each layer (assuming 4 "children" from each node in the layer above). Just draw any nodes for that layer in their appropriate position along the line and join to their parent.
– Joffan
Jul 27 at 20:04
@JMoravitz, that line is not an edge it is just to show what I mean by distance between siblings. I am sorry for confusion.
– iloveseven
Jul 27 at 20:08
@Joffan, do you mean just start drawing from the bottom given the data (set of nodes and edges) for the graph?
– iloveseven
Jul 27 at 20:09
Or you could just do it from top down... Suppose for instance that we notate vertices as sequences of $A$'s, $B$'s, $C$'s and $D$'s, corresponding to the specific ancestry of the vertex. For example, $AACB$ is the second child of $AAC$ who is the third child of $AA$ who is the first child of $A$. For each generation, just write all $n$'th generational vertices in a line in alphabetical order. No lines will ever cross in such a scenario (though some will become heavily slanted).
– JMoravitz
Jul 27 at 20:29
2
2
I do not understand what you mean by "edges intersections" and why you think they are unavoidable. It is well known that a tree is a planar graph and so admits a planar drawing. It sounds like you are wanting to draw a rooted tree where each parent vertex can have up to four children and you want to draw it in a way that avoids crossings. In your image you draw a line between siblings... that should not be done in a tree. The image you link is not a tree at all (it has a cycle).
– JMoravitz
Jul 27 at 19:54
I do not understand what you mean by "edges intersections" and why you think they are unavoidable. It is well known that a tree is a planar graph and so admits a planar drawing. It sounds like you are wanting to draw a rooted tree where each parent vertex can have up to four children and you want to draw it in a way that avoids crossings. In your image you draw a line between siblings... that should not be done in a tree. The image you link is not a tree at all (it has a cycle).
– JMoravitz
Jul 27 at 19:54
You know how many nodes are potentially on each layer (assuming 4 "children" from each node in the layer above). Just draw any nodes for that layer in their appropriate position along the line and join to their parent.
– Joffan
Jul 27 at 20:04
You know how many nodes are potentially on each layer (assuming 4 "children" from each node in the layer above). Just draw any nodes for that layer in their appropriate position along the line and join to their parent.
– Joffan
Jul 27 at 20:04
@JMoravitz, that line is not an edge it is just to show what I mean by distance between siblings. I am sorry for confusion.
– iloveseven
Jul 27 at 20:08
@JMoravitz, that line is not an edge it is just to show what I mean by distance between siblings. I am sorry for confusion.
– iloveseven
Jul 27 at 20:08
@Joffan, do you mean just start drawing from the bottom given the data (set of nodes and edges) for the graph?
– iloveseven
Jul 27 at 20:09
@Joffan, do you mean just start drawing from the bottom given the data (set of nodes and edges) for the graph?
– iloveseven
Jul 27 at 20:09
Or you could just do it from top down... Suppose for instance that we notate vertices as sequences of $A$'s, $B$'s, $C$'s and $D$'s, corresponding to the specific ancestry of the vertex. For example, $AACB$ is the second child of $AAC$ who is the third child of $AA$ who is the first child of $A$. For each generation, just write all $n$'th generational vertices in a line in alphabetical order. No lines will ever cross in such a scenario (though some will become heavily slanted).
– JMoravitz
Jul 27 at 20:29
Or you could just do it from top down... Suppose for instance that we notate vertices as sequences of $A$'s, $B$'s, $C$'s and $D$'s, corresponding to the specific ancestry of the vertex. For example, $AACB$ is the second child of $AAC$ who is the third child of $AA$ who is the first child of $A$. For each generation, just write all $n$'th generational vertices in a line in alphabetical order. No lines will ever cross in such a scenario (though some will become heavily slanted).
– JMoravitz
Jul 27 at 20:29
 |Â
show 1 more comment
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Â
draft saved
draft discarded
Â
draft saved
draft discarded
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%2f2864731%2fdraw-a-specific-graph-with-a-branching%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
2
I do not understand what you mean by "edges intersections" and why you think they are unavoidable. It is well known that a tree is a planar graph and so admits a planar drawing. It sounds like you are wanting to draw a rooted tree where each parent vertex can have up to four children and you want to draw it in a way that avoids crossings. In your image you draw a line between siblings... that should not be done in a tree. The image you link is not a tree at all (it has a cycle).
– JMoravitz
Jul 27 at 19:54
You know how many nodes are potentially on each layer (assuming 4 "children" from each node in the layer above). Just draw any nodes for that layer in their appropriate position along the line and join to their parent.
– Joffan
Jul 27 at 20:04
@JMoravitz, that line is not an edge it is just to show what I mean by distance between siblings. I am sorry for confusion.
– iloveseven
Jul 27 at 20:08
@Joffan, do you mean just start drawing from the bottom given the data (set of nodes and edges) for the graph?
– iloveseven
Jul 27 at 20:09
Or you could just do it from top down... Suppose for instance that we notate vertices as sequences of $A$'s, $B$'s, $C$'s and $D$'s, corresponding to the specific ancestry of the vertex. For example, $AACB$ is the second child of $AAC$ who is the third child of $AA$ who is the first child of $A$. For each generation, just write all $n$'th generational vertices in a line in alphabetical order. No lines will ever cross in such a scenario (though some will become heavily slanted).
– JMoravitz
Jul 27 at 20:29