Documentation improvement for graph/planar_canonical_ordering.hpp.

[Tim Gee <writetotimgee@…>]

The following undirected planar triangular graph fails to produce the correct canonical ordering. Edges: (2,4) (4,1) (1,2) (2,0) (1,0) (2,3) (3,4) (0,4) Embedding: 0 (0,1) (0,4) (0,2) 1 (1,2) (1,4) (0,1) 2 (0,2) (2,3) (2,4) (1,2) 3 (3,4) (2,3) 4 (0,4) (1,4) (2,4) (3,4) Canonical ordering produced: 0 1 4

[Tim Gee <writetotimgee@…>]

It appears that the algorithm simply requires that the first two supplied vertices are exterior and adjacent. I couldn't find this in the documentation, but it seemed apparent from the description of the algorithm that I found in "Drawing Planar Graphs using Canonical Ordering" by Goos Kant.

[Jeremiah Willcock]

Is "is biconnected and contains the edge {v1, v2} on its outer face." (what is in the current documentation) inadequate in your opinion? I.e., is this bug already fixed?

[anonymous]

Just checked: http://www.boost.org/doc/libs/1_42_0/libs/graph/doc/planar_canonical_ordering.html

Sorry, no I don't think the current documentation is adequate. The description of the algorithm output is accurate and clear (as described in the first paragraph), but the pre-requisites for the algorithm are not clear. This is particularly important, as if the inputs are not supplied correctly, the algorithm doesn't degrade nicely (it just produces a bogus ordering).

The input graph must: a) Be maximal planar. b) Have at least two vertices. c) Must contain contain the edge {v1, v2} on its outer face.

The documentation makes it clear that c) is true of the output - but isn't clear that it is also necessary in the input.

*Also, I should note that my original example didn't meet criteria (a) as it was planar triangular and maximal planar (requires [0,3] to be maximal). That's my own fault for not originally understanding the difference.

[Jeremiah Willcock]

(In [60899]) Added preconditions on graph listed in #3807; fixes #3807

[patcher@…]

The change of documentation is to confusing. The condition c) is not necessary!

In fact, the documentation says, that the embedding used for planar_canonical_ordering is a ​combinatorical embedding, not a geometrical (topological) embedding. Hence, there aren't any faces yet.

In starting with the first two vertices, the algorithm defines these both vertices to be on the outer face of an geometrical embedding, which one gets implicitly by the canonical order, see the documentation.

So the condition c) is always met and hence not needed to be mentioned. So delete this condition?

[Jeremiah Willcock]

(In [62098]) Removed third condition from list of preconditions; fixes #3807 again