Notices
Results 1 to 7 of 7

Thread: Graph theory question

  1. #1 Graph theory question 
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Well, two questions really.

    I'm working with the following graph transformation: take the directed graph and make a new graph where and .

    My first question, does anyone recognize this tranformation? Does it have an existing name or anything I can look up?

    Second, and more importantly, I need to know whether or not this transformation preserves planarity, but I don't know where to begin.

    Thanks for any advice.

    Edit: Well, I can show that it doesn't preserve planarity in all cases, but I still don't know what to call it.


    Reply With Quote  
     

  2.  
     

  3. #2 Re: Graph theory question 
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by MagiMaster
    Well, two questions really.

    I'm working with the following graph transformation: take the directed graph and make a new graph where and .

    My first question, does anyone recognize this tranformation? Does it have an existing name or anything I can look up?

    Second, and more importantly, I need to know whether or not this transformation preserves planarity, but I don't know where to begin.

    Thanks for any advice.

    Edit: Well, I can show that it doesn't preserve planarity in all cases, but I still don't know what to call it.
    Your notation is confusing.

    One would ordinarily specify a directed graph with a set of vertices and a set of edges where an edge is an ordered pair of vertices where the edge is thought of as going from to (i.e. the arrow leaves and goes to ). Note that since the arrows point in opposite directions.

    A directed graph does not have "in" and "out" vertices, but only directed edges. A vertex can have any numbrer of edges both entering it and leaving it. Think of it as bunch of does connected by line segments with arrow heads.

    So in your case I think you mean that but I have no idea what you mean with regard to .

    Planarity has nothing to do with whether or not a graph is directed. Is your question really a question about directed graphs (aka digraphs), or is about planarity. If so, are you perhaps trying to define what is known as the dual graph ? It appears not since the dual of a planar graph is a planar graph, and in fact duals are only defined for planar graphs.

    http://en.wikipedia.org/wiki/Dual_graph


    Reply With Quote  
     

  4. #3  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Sorry if my notation is confusing, but it's based on a similar construct in one of my textbooks.

    Anyway, V and E are as you said and are just normal vertex and edge sets for a normal directed graph. V' is a set containing two vertices per vertex in the original graph (one labeled v^in, one labeled v^out). E' is a set of edges that connect u^out to v^in wherever the original connected u to v, and connects v^in to v^out for every v in the original graph.

    Also, planarity may not depend on it being directed, but the construction of the new graph I'm trying to determine planarity for does. I assume the original graph is planar, and I was wondering if the new graph is. It's not always. For example, a triangle with all 6 directed edges becomes a directed K(3,3). I think I can prove that it will be planar if the original was planar and triangle-free.
    Reply With Quote  
     

  5. #4  
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by MagiMaster
    Sorry if my notation is confusing, but it's based on a similar construct in one of my textbooks.

    Anyway, V and E are as you said and are just normal vertex and edge sets for a normal directed graph. V' is a set containing two vertices per vertex in the original graph (one labeled v^in, one labeled v^out). E' is a set of edges that connect u^out to v^in wherever the original connected u to v, and connects v^in to v^out for every v in the original graph.

    Also, planarity may not depend on it being directed, but the construction of the new graph I'm trying to determine planarity for does. I assume the original graph is planar, and I was wondering if the new graph is. It's not always. For example, a triangle with all 6 directed edges becomes a directed K(3,3). I think I can prove that it will be planar if the original was planar and triangle-free.
    Ok I think I understand your construction.

    There are algotithms for determining if a graph is planar. They involve some large computer programs. A guy (a mathematician or electrical engineer and I don't recall which and I don't recall the name at the moment but he is fairly well known) who was at Bell Labs developed one in the early 1970;s or late 1960's.

    There is a general theorem that a graph is planar if and only if does not contain a subgraph that is isomorphic to within vertices of degree 2 to either K(5) or K(3,3). This is often difficult to apply as such subgraphs can be rather subtle and hard to identify.
    Reply With Quote  
     

  6. #5  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    I need to do some more work to prove my current conjecture, but I think it works. Do you recognize this transformation as anything though?
    Reply With Quote  
     

  7. #6  
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by MagiMaster
    I need to do some more work to prove my current conjecture, but I think it works. Do you recognize this transformation as anything though?
    I have never seen a constrution quite like that before, but I am not a graph theorist. It would not surprise me if someone had not done something similar in the past.

    What is your conjecture ?

    Graph theory is a part of what is called combinatorics. Combinatorics is basically that part of mathematics that relies upon counting arguments. Combinatorial arguments can easily become a complicated mess, and graph theory arguments have the reputation for doing just that. The proof of the 4-color theorem was a computer generated countng argument by exhaustion of a huge list of possible cases, and the difficult mathematics lay in proving that only the cases on the list needed to be considered. Even so the list was so long that it was not feasible for a human to work through it. Ugh.
    Reply With Quote  
     

  8. #7  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    I don't remember exactly, but I think they may have gotten the list down to something just barely within the realm of tedious but possible.

    Anyway, my conjecture is that applying that transformation to a planar triangle-free graph results in a planar graph. (It should also still be triangle-free, but that's not as important.)

    I need to show that any pre-transform graph of any subdivision of K(5) or K(3,3) would either be non-planar or contain a triangle. I think I've got that for K(3,3), but I was ignoring K(5) as the resulting graph is always bipartite. Thinking that over again, there are probably subdivisions of K(5) that are bipartite though, so I need to go back and check those again.
    Reply With Quote  
     

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •