Opened 5 years ago
Last modified 5 years ago
#19191 closed enhancement
LatticePoset: add is_planar() — at Version 33
Reported by:  jmantysalo  Owned by:  

Priority:  major  Milestone:  sage6.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:  u/ncohen/19191 (Commits, GitHub, GitLab)  Commit:  52a657ffca7acde0f622daffdbf0c066ea60887c 
Dependencies:  #19193  Stopgaps: 
Description (last modified by )
Add is_planar()
to LatticePoset
. See http://www.sciencedirect.com/science/article/pii/0095895676900241 for definition.
Change History (33)
comment:1 Changed 5 years ago by
 Branch set to u/jmantysalo/latticeposet__add_is_planar__
comment:2 Changed 5 years ago by
 Commit set to 626fc056a36488adc942d37dd5a7a531828b9b48
 Dependencies set to #19193
 Status changed from new to needs_review
comment:3 followup: ↓ 5 Changed 5 years ago by
You should work on a copy of the integerlabelled hasse diagram. Skip labels whenever you can.
comment:4 Changed 5 years ago by
 Commit changed from 626fc056a36488adc942d37dd5a7a531828b9b48 to c669ecbf2476518175f0719ba25e76cdc05f1521
Branch pushed to git repo; I updated commit sha1. New commits:
c669ecb  Use directly the Hasse diagram.

comment:5 in reply to: ↑ 3 Changed 5 years ago by
comment:6 Changed 5 years ago by
 Cc nthiery added
 Dependencies #19193 deleted
An easy review. Let's try Nicolas as a random victim for possible reviewer.
comment:7 Changed 5 years ago by
This sentence seems in contradiction with the code, which adds a (0,n1)
edge
+ A lattice is planar if it's Hasse diagram can be drawn on a + plane without crossing lines.
Nathann
comment:8 Changed 5 years ago by
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 5 years ago by
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 5 years ago by
"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 NPcomplete.
comment:11 Changed 5 years ago by
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 followup: ↓ 13 Changed 5 years ago by
This is about planarity of lattices, not posets in general.
See for example http://www.sciencedirect.com/science/article/pii/0095895676900241 or http://www.math.louisville.edu/Cumberland/slides/52%20%20Trotter.pdf slide 12.
comment:13 in reply to: ↑ 12 Changed 5 years ago by
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,n1)
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 followup: ↓ 15 Changed 5 years ago by
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 ; followup: ↓ 16 Changed 5 years ago by
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 5 years ago by
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 followup: ↓ 18 Changed 5 years ago by
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 n1 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 5 years ago by
Replying to ncohen:
Even the paper that mentions this additional edge between 0 and n1 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 5 years ago by
 Commit changed from c669ecbf2476518175f0719ba25e76cdc05f1521 to da6a1f9536ac362eef45f565515c752afdf9c84f
Branch pushed to git repo; I updated commit sha1. New commits:
da6a1f9  planar > upward_planar.

comment:20 followup: ↓ 21 Changed 5 years ago by
 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/p00512p00518.pdf etc. uses this definition.
comment:21 in reply to: ↑ 20 ; followup: ↓ 22 Changed 5 years ago by
Also http://www.math.uh.edu/~hjm/1973_Lattice/p00512p00518.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 5 years ago by
Replying to ncohen:
Also http://www.math.uh.edu/~hjm/1973_Lattice/p00512p00518.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 5 years ago by
Oh true. Coordinates. I had not noticed.
comment:24 Changed 5 years ago by
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 followup: ↓ 26 Changed 5 years ago by
Okay. You are right. This guy cites the same definition that you cite:
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://tudresden.de/Members/christian.zschalig/dateien/dissertation_zschalig
comment:26 in reply to: ↑ 25 ; followup: ↓ 27 Changed 5 years ago by
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 ; followup: ↓ 28 Changed 5 years ago by
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 evenWARNING
? It would say thatNOTE
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 ; followup: ↓ 29 Changed 5 years ago by
Replying to ncohen:
I still hesitate over this
is_planar
andis_upward_planar
. If you really think that the first is better then let's do this, but if you believe that anybody who looks foris_planar
would also think of tryingis_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 ; followup: ↓ 30 Changed 5 years ago by
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 ; followup: ↓ 31 Changed 5 years ago by
comment:31 in reply to: ↑ 30 Changed 5 years ago by
 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 5 years ago by
 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
comment:33 Changed 5 years ago by
 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.
Ready for review, BUT please note the dependency: This will work when #19193 has been fixed.
New commits:
Added is_planar() to lattices.