how to plot graph without intersection?

I have this graph

E=[1  2;1  5;2  3;2  4;2  5;3  4;4  5;4  7;4  9;5  6;6  11;6  12;6  13;7  8;7  9;9  10;9  14;10  11;12  13;13  14]

when I use graph code,

G=graph(E(:,1),E(:,2))
h=plot(G)

plots graph with intersection.

Is there any codes that plot graph without intersection?

[KSSV]

The intrsection depends on E. YOu have to provide E so that the points don't intersect.

[NA]

How can I do that?

Answer 1

[Guillaume]

First, why is it a problem that some of the edges intersect in the plot? The plot is not ambiguous in any way, even if there are intersection between edges, the nodes are clearly marked. With a sufficiently complex graph, it's not going to be possible to plot it with some edges intersecting.

You can always experiment with the various Layout options of plot. e.g.

h = plot(G, 'Layout', 'circle')

although I've not found any default layout that doesn't have intersecting edges with your graph.

If you can work out yourself a node arrangement that doesn't lead to intersecting edges, you can always specify the position of the nodes when you call plot. Alternatively, you can let plot do its thing and manually move some nodes afterward:

h = plot(G)
h.XData([10 11]) = h.XData([7 8])

The above results in no intersection but as I've said with a sufficiently complex graph it may be impossible to plot it without intersections

[NA]

I want to find a face of graph.

I only need to draw graph without intersection

[Guillaume]

I have no idea what that means: "I want to find a face of graph"

I only need to draw graph without intersection

And

h = plot(G)
h.XData([10 11]) = h.XData([7 8])

doesn't do it for you?

[NA]

it is work for my graph, but how can do you find [10 11] and [7 8]?

it means that of I have a other graph, how I can write this?

[Guillaume]

There is no function built into matlab that can do it automatically for any arbitrary graph. plot does its best, but it's not its priority to avoid intersection because for most people they don't matter (and I still don't understand why they matter to you).

You will either have to write your own plotting function (or at the very least work out an algorithm that find the optimal position of the nodes for your use case), something that is not trivial at all (probably a PhD worth) or do it manually by looking at the graph and manually moving nodes until there's no intersection.

In this particular case, I just looked at the graph and noticed that if I positioned node 10 at the same X position as node 7 and node 11 at the same X position as node 8, there was no intersection.

Answer 2

[Christine Tobler]

It sounds like you are looking for functionality related to planar graphs. MATLAB does not have any methods specific to this, but the MATLAB BGL on the File Exchange provides some functionality (checking if a graph is planar, and computing a straight-line drawing in that case).

I'd be interested to learn some more about your application. Are you looking to extract all the faces of the straight-line drawing of your graph? And what is the next step to do with these faces?

[NA]

I used MATLAB BGL, the planarity_test says that the graph is planar or not.

In my case it is planar. How can I 'computing a straight-line drawing'?

I want to find faces of planar graph.

[Christine Tobler]

There's a function chrobak_payne_straight_line_drawing (note I haven't tried any of these myself, I'm just reading the descriptions). From the help text of that function:

% X = chrobak_payne_straight_line_drawing(A) generates coordinates for each
% vertex such that a planar graph A can be drawn without any edge
% crossings.  This function reports an error if A is not planar.
%
% [X,p,ei,ej] = ... returns additional information.  p is a
% canonical planar ordering of the vertices, and [ei ej] are additional
% edges required to make A a maximal_planar graph.

Please let me know if this is what you are looking for, or if you require some other data that specifies the faces of this drawing.

[NA]

When I use this function chrobak_payne_straight_line_drawing(A), it gives me this graph. Althougth it draws planar but it chang the face 2,4,5.

[Christine Tobler]

Change with respect to what? Where are you comparing to that has a face 2, 4, 5?

[NA]

When I plot the graph, G=graph(E(:,1),E(:,2))

h=plot(G)

I have face 2,4,5.

[Walter Roberson]

And so does the planar graph has a face 2, 4, 5.

Planar embeddings are not unique, and cannot be used to extract the information you are looking for.

[Guillaume]

You have to explain why some loops/faces are included in your graph, and not others. E.g. why isn't [5, 6, 13, 14, 9, 4] in your S?

[Christine Tobler]

I agree with Guillaume: To give a general method of finding s, we need a general and unique description of what s needs to be (which will then also tell us what makes s different from M).

Do you want faces that are all triangles? (But M has some faces that are not triangles). From your example, I don't know what the general criterion is.