Opened 3 years ago

Closed 3 years ago

#19191 closed enhancement (fixed)

LatticePoset: add is_planar()

Reported by: jmantysalo Owned by:
Priority: major Milestone: sage-6.9
Component: combinatorics Keywords:
Cc: nthiery Merged in:
Authors: Nathann Cohen, Jori Mäntysalo Reviewers: Jori Mäntysalo, Nathann Cohen
Report Upstream: N/A Work issues:
Branch: 52a657f (Commits) Commit: 52a657ffca7acde0f622daffdbf0c066ea60887c
Dependencies: #19193 Stopgaps:

Description (last modified by jmantysalo)

Add is_planar() to LatticePoset. See http://www.sciencedirect.com/science/article/pii/0095895676900241 for definition.

Change History (35)

comment:1 Changed 3 years ago by jmantysalo

  • Branch set to u/jmantysalo/latticeposet__add_is_planar__

comment:2 Changed 3 years ago by jmantysalo

  • Commit set to 626fc056a36488adc942d37dd5a7a531828b9b48
  • Dependencies set to #19193
  • Status changed from new to needs_review

Ready for review, BUT please note the dependency: This will work when #19193 has been fixed.


New commits:

626fc05Added is_planar() to lattices.

comment:3 follow-up: Changed 3 years ago by ncohen

You should work on a copy of the integer-labelled hasse diagram. Skip labels whenever you can.

comment:4 Changed 3 years ago by git

  • Commit changed from 626fc056a36488adc942d37dd5a7a531828b9b48 to c669ecbf2476518175f0719ba25e76cdc05f1521

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

c669ecbUse directly the Hasse diagram.

comment:5 in reply to: ↑ 3 Changed 3 years ago by jmantysalo

Replying to ncohen:

You should work on a copy of the integer-labelled hasse diagram. Skip labels whenever you can.

True. Corrected. Thanks!

I left this technically as needs_review, because this should be OK after #19193.

comment:6 Changed 3 years ago by jmantysalo

  • Cc nthiery added
  • Dependencies #19193 deleted

An easy review. Let's try Nicolas as a random victim for possible reviewer.

comment:7 Changed 3 years ago by ncohen

This sentence seems in contradiction with the code, which adds a (0,n-1) edge

+        A lattice is planar if it's Hasse diagram can be drawn on a
+        plane without crossing lines.

Nathann

comment:8 Changed 3 years ago by jmantysalo

Next paragraph explains what is the meaning of Hasse diagram (i.e. have a right direction). But OK, I'll think better phrasing.

comment:9 Changed 3 years ago by ncohen

http://www.sciencedirect.com/science/article/pii/009589567790048X

The abstract of this paper is rather clear on what a planar poset is supposed to be.

Nathann

comment:10 Changed 3 years ago by jmantysalo

"A partially ordered set (poset) is planar if it has a planar Hasse diagram."? Quite short...

How about

"A lattice is planar if it has a planar Hasse diagram --- that is, it can be drawn to a plane without crossing lines and every covering relationg directed upwards."?

And yes, this function could be defined on a general poset. But then it is NP-complete.

comment:11 Changed 3 years ago by ncohen

Sorry Jori, I do not follow you: the paper whose link I posted in a previous comment says that a poset is planar if its hasse diagram is planar. I see no mention of an additional edge (that you add in your code), and it is clearly polynomial at all times.

comment:12 follow-up: Changed 3 years ago by jmantysalo

comment:13 in reply to: ↑ 12 Changed 3 years ago by ncohen

This is about planarity of lattices, not posets in general.

The paper I sent you previously says that a *Poset* is planar if its hasse diagram is planar.

The first paragraph (not the abstract) in the first paper that you mentionned says that the definition is (naturally) the same for posets, i.e. that they are planar whenever their hasse diagram is planar.

What the first paper claims in its title is that you can *chose* to add the (0,n-1) edge without changing the property.

What the slideshow says in its 12th page looks contradictory with the two papers above. If you can find the paper it quotes, perhaps that will clarify it.

Nathann

comment:14 follow-up: Changed 3 years ago by jmantysalo

There seems to be same concept in plain graph theory: upward planar DAG. See https://en.wikipedia.org/wiki/Upward_planar_drawing

The abstract of first paper I mentioned starts with "It is shown that a finite lattice is planar if and only if the (undirected) graph obtained from its (Hasse) diagram by adding an edge between its least and greatest elements is a planar graph." And this makes no sense if planarity of lattices would equal to planarity of graphs.

The question is about meaning of Hasse diagram. Should we say that it is a special type of DAG, or that it is a DAG drawn with a limitation? I think that writers think about latter.

But of course 1) this must be made very clear in the documentation, and 2) it might have interesting question in it own to look properties of posets with planar covering relations graph.

comment:15 in reply to: ↑ 14 ; follow-up: Changed 3 years ago by ncohen

The abstract of first paper I mentioned starts with "It is shown that a finite lattice is planar if and only if the (undirected) graph obtained from its (Hasse) diagram by adding an edge between its least and greatest elements is a planar graph." And this makes no sense if planarity of lattices would equal to planarity of graphs.

It *does* make sense. It means that if a lattice is planar, then there is a drawing of it in which the top and bottom elements appear in the same face.

The question is about meaning of Hasse diagram.

As a reviewer, I just want to make sure that what the user will understand is what actually happens.

Nathann

comment:16 in reply to: ↑ 15 Changed 3 years ago by jmantysalo

Replying to ncohen:

As a reviewer, I just want to make sure that what the user will understand is what actually happens.

How about

"A lattice is planar if it's Hasse diagram has an upward planar drawing. In other words, planar lattice can be drawn without crossing lines and every covering relation directed upwards."

?

comment:17 follow-up: Changed 3 years ago by ncohen

Jori,

Up to now, in all papers that I have seen, a Poset is defined to be planar when its hasse diagram is planar. Have you even found one paper that defines it differently?

If there is to be a Lattice.is_planar or a Poset.is_planar, I expect it to be self._hasse_diagram.is_planar(), and nothing else. Even the paper that mentions this additional edge between 0 and n-1 uses *this* definition (without the additional edge) and apparently proves that you can add this edge without changing the property.

The least I can say is that I *know* that some people would be entitled to believe that Lattice.is_planar does not add any edge, even without reading the documentation (did you ever read the documentation of is_even ?). And those must not be mislead.

If you want to implement another definition, it will have to be under another name.

Nathann

comment:18 in reply to: ↑ 17 Changed 3 years ago by jmantysalo

Replying to ncohen:

Even the paper that mentions this additional edge between 0 and n-1 uses *this* definition (without the additional edge) and apparently proves that you can add this edge without changing the property.

No. Hasse diagram for BooleanLattice(3) is planar, but it has no upward planar drawing.

If you want to implement another definition, it will have to be under another name.

That's OK.

comment:19 Changed 3 years ago by git

  • Commit changed from c669ecbf2476518175f0719ba25e76cdc05f1521 to da6a1f9536ac362eef45f565515c752afdf9c84f

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

da6a1f9planar -> upward_planar.

comment:20 follow-up: Changed 3 years ago by jmantysalo

  • Dependencies set to #19193
  • Status changed from needs_review to needs_info

I committed a version with new name for the function.

But still, I do not understand. The term planar lattice is used by D. Kelly and I. Rival in Canadian Journal of Mathematics, june 1975. And it uses the definition I suggested at start. Also http://www.math.uh.edu/~hjm/1973_Lattice/p00512-p00518.pdf etc. uses this definition.

comment:21 in reply to: ↑ 20 ; follow-up: Changed 3 years ago by ncohen

Also http://www.math.uh.edu/~hjm/1973_Lattice/p00512-p00518.pdf etc. uses this definition.

At the bottom of page 1 in this paper I read "P is planar if it has a planar diagram", where "diagram" is defined, just above, to be equal to the hasse diagram.

Nathann

comment:22 in reply to: ↑ 21 Changed 3 years ago by jmantysalo

Replying to ncohen:

Also http://www.math.uh.edu/~hjm/1973_Lattice/p00512-p00518.pdf etc. uses this definition.

At the bottom of page 1 in this paper I read "P is planar if it has a planar diagram", where "diagram" is defined, just above, to be equal to the hasse diagram.

"A diagram of P is a set of n points in the (x, y)-plane - - together with certain arcs between these points such that: a) If p_i covers p_j then y_i > y_j - -".

comment:23 Changed 3 years ago by ncohen

Oh true. Coordinates. I had not noticed.

comment:24 Changed 3 years ago by ncohen

I'm trying to find some recent publication in which I can check this terminology. It seems indeed that those guys could say that "the diagram is planar" and talk about this kind of embedding without saying it, but it sounds so absurdly misleading that I want to see it written in a paper written after I was born.

comment:25 follow-up: Changed 3 years ago by ncohen

Okay. You are right. This guy cites the same definition that you cite:

http://mathoverflow.net/questions/198116/is-a-distributive-lattice-planar-iff-it-admits-no-b3-sublattice

And, more importantly, this book [1] on page 93 (bottom). Or this dissertation [2] page 23.

So you were right from the beginning. And I still can't believe how on earth they thought wise to have two such definitions coexist when they are so close to each other. We end up with results like "there are posets whose hasse diagram is not planar, though the hasse diagram (as a graph) is planar".

Okay. So what do we do:

I obviously prefer it to be named "is_upward_planar", but that just says that I would prefer the standard poset terminology to be "is upward planar". Truth it that people working on posets expect it to be written "is_planar", so that's probably how it should be named.

Sorry for the loss of time. I guess I just needed some recent publications which did what your 72 paper does, i.e. say explicitly that planarity is not graph planarity.

I will now take your branch and work a bit on the documentation, just to make sure that people like me would not make the mistake if they read it. If they just read the function's name, well, they are lost.

Nathann

[1] http://www.springer.com/us/book/9783319064123 [2] https://tu-dresden.de/Members/christian.zschalig/dateien/dissertation_zschalig

comment:26 in reply to: ↑ 25 ; follow-up: Changed 3 years ago by jmantysalo

Replying to ncohen:

So you were right from the beginning. And I still can't believe how on earth they thought wise to have two such definitions coexist when they are so close to each other. - -

Well, mathematicians do not always behave logically. :=).

1) Is it technically possible to give positive review to a ticket like this, as this depends on closed ticket not yet at newewst beta? 2) This obviously needs clarification in documentation. But NOTE or even WARNING? It would say that NOTE is enought. 3) Is there easy way to undo last commit on ticket? Not that it would be that big thing in this specific case do by hand.

comment:27 in reply to: ↑ 26 ; follow-ups: Changed 3 years ago by ncohen

Well, mathematicians do not always behave logically. :=).

-_-

1) Is it technically possible to give positive review to a ticket like this, as this depends on closed ticket not yet at newewst beta?

The only thing that we must preserve is Volker's own happiness. It does not matter what you and I have on our hard drive: when a ticket is closed, it means that Volker's latest release contains the ticket. So you can assume that it is already applied.

2) This obviously needs clarification in documentation. But NOTE or even WARNING? It would say that NOTE is enought.

I agree. I only have a note in the version I am working on.

3) Is there easy way to undo last commit on ticket?

Yeah yeah. Look at 'git rebase -i', I use this all the time (look for 'squashing'). But don't worry about this, I am working on the branch and will push it shortly.

I still hesitate over this is_planar and is_upward_planar. If you really think that the first is better then let's do this, but if you believe that anybody who looks for is_planar would also think of trying is_upward_planar then the second is obviously safer. Tell me how you want it done, and I will update the branch accordingly.

Nathann

comment:28 in reply to: ↑ 27 ; follow-up: Changed 3 years ago by jmantysalo

Replying to ncohen:

I still hesitate over this is_planar and is_upward_planar. If you really think that the first is better then let's do this, but if you believe that anybody who looks for is_planar would also think of trying is_upward_planar then the second is obviously safer. Tell me how you want it done, and I will update the branch accordingly.

Googling "upward planar lattice" seems to found nothing. I guess it is good reason to have is_planar(), as it seems to be only used term.

(In the future we should not have problems like this. Just wait until SageMath is The Software and all questions about "what is exact definition of...?" will be answered "Sage defines...". ;=))

comment:29 in reply to: ↑ 28 ; follow-up: Changed 3 years ago by ncohen

Googling "upward planar lattice" seems to found nothing. I guess it is good reason to have is_planar(), as it seems to be only used term.

Okay, done at u/ncohen/19191. Note that I rewrote history.

(In the future we should not have problems like this. Just wait until SageMath is The Software and all questions about "what is exact definition of...?" will be answered "Sage defines...". ;=))

Yeah. Well if that's the case then I will regret even more this Poset.is_planar. At least I will have this trac tickets to use for my own defense :-P

Nathann

comment:30 in reply to: ↑ 29 ; follow-up: Changed 3 years ago by jmantysalo

Replying to ncohen:

Okay, done at u/ncohen/19191. Note that I rewrote history.

Seems good.

Remove dependency, as it is now handled differently. This will clash with #19123, but I can rebase it later.

comment:31 in reply to: ↑ 30 Changed 3 years ago by ncohen

  • Reviewers set to Nathann Cohen
  • Status changed from needs_info to needs_review

Seems good.

Then if you agree with it you can change the branch's name on this ticket, and set it to positive_review for inclusion.

Nathann

comment:32 Changed 3 years ago by jmantysalo

  • Authors changed from Jori Mäntysalo to Nathann Cohen, Jori Mäntysalo
  • Branch changed from u/jmantysalo/latticeposet__add_is_planar__ to u/ncohen/19191
  • Commit changed from da6a1f9536ac362eef45f565515c752afdf9c84f to 52a657ffca7acde0f622daffdbf0c066ea60887c
  • Dependencies #19193 deleted
  • Reviewers changed from Nathann Cohen to Jori Mäntysalo, Nathann Cohen

Going to compile to be sure.


New commits:

3452935Added is_upward_planar() to lattices.
52a657ftrac #19191: Additional documentation

comment:33 Changed 3 years ago by jmantysalo

  • Dependencies set to #19193
  • Description modified (diff)
  • Status changed from needs_review to positive_review

Duh, an example still depends on #19193. Added that. Now this seems to ready to go.

comment:34 in reply to: ↑ 27 Changed 3 years ago by nthiery

Replying to ncohen:

I still hesitate over this is_planar and is_upward_planar.

For whatever it's worth (and it's late in the review process), I am also hesitant. In papers it is often less of an issue to use short names as the context helps removing ambiguities. So if someone comes up with a good explicit is_xxx_planar suggestion (I don't have one), that looks appealing. But that's just my 2cents; please proceed as you see fit.

Cheers,

Nicolas

comment:35 Changed 3 years ago by vbraun

  • Branch changed from u/ncohen/19191 to 52a657ffca7acde0f622daffdbf0c066ea60887c
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.