1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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