Hopcroft-Tarjan Planarity Algorithm (problem with edge weighting?)

Perhaps I'm too tired but is there a problem with the edge weighting
scheme in this algorithim? Consider the following graph:

__________________
| |
1___2_______3_____4
|\ |
| \_____5
| |
|_______6

formula for weight (phi) of edge vw:
if frond (i.e. w<v) phi = 2 * w
otherwise if LOWPT2 = v phi = 2 * LOWPT1
otherwise if LOWPT2 < v phi = 2 * LOWPT1 + 1

so the edges have the following weights:
phi = 2 (1,2) (2,3) (3,4) (4,1)
phi = 4 (3,5) (5,2) (5,6) (6,2)

The first path (the cycle) is obviously 1,2,3,4,1
But how about the second and third paths? 3,5,2 then 5,6,2 or 3,5,6,2
then 5,2 ?

.

Relevant Pages

  • Hopcroft-Tarjan Planarity Algorithm (problem with edge weighting?)
    ... Perhaps I'm too tired but is there a problem with the edge weighting ... Consider the following graph: ... formula for weight (phi) of edge vw: ... The first path is obviously 1,2,3,4,1 ...
    (comp.theory)
  • Re: Graph Problem
    ... Graph G, and you are given a set of vertices. ... I think this can be done by finding shortest path between every two ... Indeed it sounds like you want a minimum spanning tree. ... that the edges have no weighting. ...
    (comp.theory)