0

I have two questions;

  1. What is the name of the graph (or circuit) which goes along the outer vertices of existing nodes.

  2. What will be the formal definition of that graph.

for the simplicity, I have added a sample figure and the red highlighted graph is what I wanted.

enter image description here

If I show how I got this outer vertices;

enter image description here

I have set of sub graphs. So I got UNION and INTERSECTION, then got the DIFFERENCE. Do this one after the other, Finally I ended with a graph which is similar to MY RED EDGE GRAPH.

So the final graph which I got was {1,2,6,7,9,8,10,11,10,7,6,5,3,4,3,1} if i start from 1.

PLEASE TELL ME WHETHER I AM USING CORRECT THING OR NOT AS I AM COMING TO END OF MY WORK.

niro
  • 947
  • 3
  • 13
  • 30
  • 3
    You need to define `outer vertices` for that. AFAIK definition of `outer` depends on geometrical position of point, and, thus, could not be applied to graph theory. You can draw this graph in infinite number of ways. If position does matter it's not clearly a graph. Check out [convex hull](http://en.wikipedia.org/wiki/Convex_hull) if you want to approach sets of points. – default locale Mar 23 '13 at 11:42
  • @default locale: i am not sure whether I got you properly. in my case, my vertices are fixed based on the topology. so that, I can not go for many options and I have fixed locations for the graph. in that sense plz clarify this again. I am not using many points to make convex hulls. – niro Mar 23 '13 at 11:53
  • graph is just a set of vertices and edges. Edges are not equivalent to lines and graph doesn't have to be planar. If you have points with given coordinates, use the link in previous comment. – default locale Mar 23 '13 at 11:56
  • @default locale: Actually, I am constructing this red edge graph using other sub graphs. As my objective is to avoid inside edges. Here, inside edges are obtained by the intersection. – niro Mar 23 '13 at 11:56
  • so, what are the outer vertices on last picture? – default locale Mar 23 '13 at 12:16
  • @default locale: 1,2,6,7,9,8,10,11,10,7,6,5,3,4,3,1 – niro Mar 23 '13 at 12:19
  • let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/26777/discussion-between-niro-and-default-locale) – niro Mar 23 '13 at 12:20
  • How do you can to add this circle graph (2,3,12)? – amin k Mar 29 '13 at 23:45

1 Answers1

3

You may be trying to define some kind of geometric hull, but surely not a graph property. These two graphs are equivalent and indistinguishable a far as Graph Theory goes:

Mathematica graphics

Edit Perhaps this old answer of mine may help you

Community
  • 1
  • 1
Dr. belisarius
  • 60,527
  • 15
  • 115
  • 190
  • yes i got it. but in this case, I am composing sub-graphs and make a big one which goes along red nodes. I will update the post. – niro Mar 23 '13 at 12:09
  • PLease have a look my explanation. and let me know whether this process follows graph concepts – niro Mar 23 '13 at 12:15
  • 1
    @niro Sorry, I don't understand your last update. Graphs don't have "inside" and "outside" properties, those are topological concepts. – Dr. belisarius Mar 23 '13 at 12:26