Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Conflict bridges of graph, where it from

  1. Mar 17, 2006 #1


    User Avatar

    I've been taught in lecture last week about graph planarity testing. But the main idea of conflict bridges I still don't understand. Then I search online, from wikipedia to mathworld, there are nothing about this bridge concept. I begin to wonder if this idea is a standard method to do this kind of testing. Are these definitions look familiar to you? Could you give me a reference where it's from?

    if H is a subgraph of G, an H-bridge of G is either:
    1. an dege not in H whose endvertices are in H, or
    2. a component of G-V(H) together with the edges ( and vertices of attachment) that connect it to H.

    Conflicting Bridges
    Given a cycle H in graph G, two H-bridges A, B conflict if they have three common vertices of attchment or there are four vertices v1 v2 v3 v4 in cyclic order on H such that v1 v3 are vertices of attachment of A and v2 v4 are vertices of attchment of B.

    Planarity testing
    Suppose Gis not a tree. Let H be a cycle in G:
    1 if any H-bridge of G is non-planar the G is non-planar.
    1 if three H-bridges of G mutually conflict, then G is non-planar.

    At last, if you are my lecturor, and think I plagiarized your lecture notes, please PM me.
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted