[Boost-bugs] Bug in function boyer_myrvold_planarity_test?

Subject: [Boost-bugs] Bug in function boyer_myrvold_planarity_test?
From: Hailong Yao (hailongyao_at_[hidden])
Date: 2009-06-15 20:20:59

Hi,

Is this a bug in function boyer_myrvold_planarity_test? Or did I wrongly use
the function?

I constructed an undirected graph of 46 nodes, where the edges are:
(0,22) (3,22) (0,23) (8,23) (1,24) (5,24) (1,25) (6,25) (1,26) (7,26) (2,27)
(4,27) (2,28) (5,28) (6,29) (7,29) (6,30) (8,30) (7,31) (8,31) (7,32) (9,32)
(8,33) (9,33) (10,34) (19,34) (10,35) (20,35) (11,36) (12,36) (11,37)
(20,37) (12,38) (13,38) (12,39) (14,39) (15,40) (17,40) (15,41) (18,41)
(16,42) (18,42) (17,43) (18,43) (19,44) (21,44) (20,45) (21,45) (1,17)
(5,17) (5,19) (5,21) (7,10) (7,19) (9,10) (9,11) (9,19)

Then I use boyer_myrvold_planarity_test to identify the Kuratowski subgraph.
The output (i.e., edges in the identified Kuratowski subgraph) is as
follows:
(0,23) (8,23) (1,24) (5,24) (1,25) (6,25) (1,26) (7,26) (6,30) (8,30) (7,32)
(9,32) (10,34) (19,34) (10,35) (20,35) (11,37) (20,37) (21,44) (20,45)
(21,45) (5,19) (5,21) (7,10) (9,11) (9,19)

When I use function is_kuratowski_subgraph to test if it is really a
Kuratowski subgraph. It says "Yes".

However, it is obvious that the edges in the identified Kuratowski subgraph
is not minimal, e.g., edge (0,23) can be removed because node 0 is only
connected with one edge in the subgraph. Is this a bug in function
boyer_myrvold_planarity_test? Can anyone help me to solve this? Thanks very
much.

Regards,
Hailong Yao