Planar graph layout does not respect clockwise ordering of neighbors in combinatorial embedding

[rburing]

Consider the claw S₃:

S3 = Graph([[0,1,2,3],[[0,1],[0,2],[0,3]]])

The following combinatorial embedding is respected in the planar layout (the neighbors are in the given clockwise order):

S3.set_embedding({0: [1,2,3], 1: [0], 2: [0], 3: [0]})
S3.layout('planar', save_pos=True)
S3.show()

While this one isn't:

S3.set_embedding({0: [3,2,1], 1: [0], 2: [0], 3: [0]})
S3.layout('planar', save_pos=True)
S3.show()

In the latter, the neighbors are in the counterclockwise order (in fact the picture is the same as the former).

Strictly speaking, layout_planar (which is called by layout) does not promise to use the combinatorial embedding. But it does provide an option on_embedding which I assume should allow this:

S3.set_pos(S3.layout_planar(on_embedding={0: [3,2,1], 1: [0], 2: [0], 3: [0]}))

Still, the combinatorial embedding is not respected. I think this is because in layout_planar the line G.is_planar(set_embedding=True) executed unconditionally (totally ignoring on_embedding).

Component: graph theory

Keywords: planar, clockwise, embedding

Author: Hendrik Schrezenmaier

Branch/Commit: b941f18

Reviewer: David Coudert

Issue created by migration from https://trac.sagemath.org/ticket/28152

[hensc]

Branch: u/gh-hensc/planar_graph_layout_does_not_respect_clockwise_ordering_of_neighbors_in_combinatorial_embedding

[hensc]

New commits:

13c4252	Fixed bug concerning the combinatorial embedding of Schnyder drawings
dc57871	Added doctest and fixed bugs to pass doctests

[hensc]

Author: Hendrik Schrezenmaier

[hensc]

Commit: dc57871

[dcoudert]

comment:3

A few stylistic comments. Recall that comments must be in 80 columns mode and that we do our best to follow the pep8 conventions.

-        TESTS::
-
-            Check the dependence of the computed position on the given
-            combinatorial embedding (:trac:`28152`).
+        TESTS:
+
+        Check the dependence of the computed position on the given
+        combinatorial embedding (:trac:`28152`)::

-    all triangles, and return the set of newly created edges. Also comb_emb
+    all triangles, and return the set of newly created edges. Also ``comb_emb``

pep8

-            comb_emb[w].insert(comb_emb[w].index(x),u)
-            comb_emb[u].insert(comb_emb[u].index(v),w)
+            comb_emb[w].insert(comb_emb[w].index(x), u)
+            comb_emb[u].insert(comb_emb[u].index(v), w)

80 columns mode

-    # Up to this point we did not take the order of the external face into account.
-    # Since the combinatorial embedding of a triangulated is only unique up to
-    # the choice of the outer face and reflection, this might lead to a reflection
-    # of the Schnyder drawing resulting from this labeling which is not conformal
-    # with comb_emb any longer. Therefore, we might have to swap the labels 1 and 2.
+    # Up to this point we did not take the order of the external face into
+    # account. Since the combinatorial embedding of a triangulation is unique
+    # up to the choice of the outer face and reflection, this might lead
+    # to a reflection of the Schnyder drawing resulting from this labeling which
+    # is not conformal with comb_emb any longer. Therefore, we might have to
+    # swap the labels 1 and 2.

I also did minor changes in above text. Please check.

Passes all tests with py3. I have not fully tested yet de functionality.

[fchapoton]

comment:4

one failing doctest in src/sage/graphs/planarity.pyx, see patchbot report

[rburing]

comment:6

Thanks for the effort so far. I suggest also to add a line of documentation, at least in layout_planar, explaining which combinatorial embedding is used when, e.g. "If on_embedding is provided then that combinatorial embedding is used for the layout. Otherwise: if a combinatorial embedding is set (e.g. using set_embedding) then that one is used, and if no combinatorial embedding is set then one is computed." (modify it to make it a true statement).

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

2b7870d	pep8
3c74ff6	Removed special case of path of length 2

[sagetrac-git]

Changed commit from dc57871 to 3c74ff6

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

b3f4308

fixed typo

[sagetrac-git]

Changed commit from 3c74ff6 to b3f4308

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

2248ce7

fixed typo

[sagetrac-git]

Changed commit from b3f4308 to 2248ce7

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

ec8e7b5

edited documentation

[sagetrac-git]

Changed commit from 2248ce7 to ec8e7b5

[hensc]

comment:12

I fixed the pep8 and also fixed the bug that made the doctest fail.
Now the patchbot passed all tests.

I also made the documentation more precise about which combinatorial embedding is used. But unfortunately it is not as rburing thought (and I think to be more intuitive, too) that on_embedding is always used if it is given. If set_embedding is set to True, then on_embedding is ignored. So the question is if we could/should/want to change this behavior.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

07c6624

Merge branch 'develop' of git://github.com/sagemath/sage into t/28152/planar_graph_layout_does_not_respect_clockwise_ordering_of_neighbors_in_combinatorial_embedding

[sagetrac-git]

Changed commit from ec8e7b5 to 07c6624

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

da464d2

Merge branch 'develop' of git://github.com/sagemath/sage into t/28152/planar_graph_layout_does_not_respect_clockwise_ordering_of_neighbors_in_combinatorial_embedding

[sagetrac-git]

Changed commit from 07c6624 to da464d2

[hensc]

comment:15

please review

[dcoudert]

comment:16

I have only a minor comment. Otherwise seems ok.

-            for (v,w) in labels[u]:
-                if labels[u][(v,w)] == 1:
-                    labels[u][(v,w)] = 2
-                elif labels[u][(v,w)] == 2:
-                    labels[u][(v,w)] = 1
+            for v, w in labels[u]:
+                if labels[u][v, w] == 1:
+                    labels[u][v, w] = 2
+                elif labels[u][v, w] == 2:
+                    labels[u][v, w] = 1

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

b828839	minor improvement of code style
b941f18	Merge branch 'develop'

[sagetrac-git]

Changed commit from da464d2 to b941f18

[dcoudert]

Reviewer: David Coudert

[dcoudert]

comment:18

OK, LGTM.

[vbraun]

Changed branch from u/gh-hensc/planar_graph_layout_does_not_respect_clockwise_ordering_of_neighbors_in_combinatorial_embedding to b941f18