[Boost-bugs] [Boost C++ Libraries] #9677: make_biconnected_planar failure when working with custom planar embedding

Subject: [Boost-bugs] [Boost C++ Libraries] #9677: make_biconnected_planar failure when working with custom planar embedding
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2014-02-17 19:46:00

#9677: make_biconnected_planar failure when working with custom planar embedding
---------------------------------------+----------------------
 Reporter:  Jakub Oćwieja <netkuba@…>  |      Owner:  jewillco
     Type:  Bugs                       |     Status:  new
Milestone:  To Be Determined           |  Component:  graph
  Version:  Boost 1.53.0               |   Severity:  Problem
 Keywords:                             |
---------------------------------------+----------------------
 Using make_biconnected_planar function with a planar graph G and its
 custom embedding results in a graph, which is no longer planar.

 The problem doesn't occur when embedding G with
 boyer_myrvold_planarty_test.

 The custom planar embedding of a graph G with 11 vertices and 18 edges is
 (each group is a counter clock-wise list of edges adjacent to a vertex):

 0 - 1 : 0
 0 - 8 : 15

 0 - 1 : 0
 1 - 2 : 2
 4 - 1 : 3
 1 - 3 : 1

 1 - 2 : 2
 2 - 3 : 5
 2 - 4 : 4

 1 - 3 : 1
 3 - 4 : 6
 2 - 3 : 5

 4 - 1 : 3
 2 - 4 : 4
 3 - 4 : 6

 5 - 6 : 7
 5 - 8 : 9
 7 - 5 : 8

 5 - 6 : 7
 6 - 7 : 10
 6 - 9 : 12
 8 - 6 : 11

 7 - 5 : 8
 7 - 8 : 13
 9 - 7 : 14
 6 - 7 : 10

 5 - 8 : 9
 8 - 6 : 11
 8 - 9 : 16
 0 - 8 : 15
 7 - 8 : 13

 6 - 9 : 12
 9 - 7 : 14
 9 - 10 : 17
 8 - 9 : 16

 9 - 10 : 17

 An example program is attached.

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/9677>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.