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?(adsbygoogle = window.adsbygoogle || []).push({});

H-bridges:

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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

Can you offer guidance or do you also need help?

Draft saved
Draft deleted

**Physics Forums | Science Articles, Homework Help, Discussion**