1. Not finding help here? Sign up for a free 30min 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!

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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you help with the solution or looking for help too?

Similar Discussions: Conflict bridges of graph, where it from