Opened 11 years ago
Closed 2 years ago
#6236 closed enhancement (fixed)
find the dual graph of a planar graph
Reported by:  jason  Owned by:  rlm 

Priority:  major  Milestone:  sage8.1 
Component:  graph theory  Keywords:  
Cc:  brunellus, nvcleemp  Merged in:  
Authors:  Moritz Firsching  Reviewers:  David Coudert 
Report Upstream:  N/A  Work issues:  
Branch:  922b58b (Commits)  Commit:  922b58b454a8c4af6758b7d4b149b629209cb469 
Dependencies:  Stopgaps: 
Description
Working code is here: http://sagenb.org/home/pub/417/
The worksheet also includes code which lists the faces of a planar embedding of a graph.
Change History (33)
comment:1 Changed 11 years ago by
comment:2 Changed 11 years ago by
 Component changed from algebra to graph theory
 Owner changed from tbd to rlm
This should be filed in "graph theory".
comment:3 Changed 10 years ago by
 Report Upstream set to N/A
 Type changed from defect to enhancement
comment:4 Changed 8 years ago by
 Cc brunellus added
comment:5 followup: ↓ 7 Changed 7 years ago by
 Cc nvcleemp added
Hmm, I'm interested in this functionality, so if nobody else is planning on working on it, I would be up to it.
It seems that the code given as an example only 'works' for 3edgeconnected simple planar graphs. Is this sufficient, or should we also try to make it work for other graphs? Supporting multigraphs might depend on #14657.
comment:6 Changed 7 years ago by
IIRC, the only case I was interested in was cubic planar graphs, and it seemed that there was a nice simplification in that case. Anyways, go for it!
comment:7 in reply to: ↑ 5 Changed 5 years ago by
Hi,
I'm interested in this functionality too!
It seems that the code given as an example only 'works' for 3edgeconnected simple planar graphs. Is this sufficient, or should we also try to make it work for other graphs? Supporting multigraphs might depend on #14657.
What do you mean by 'works'? I don't know enough graph theory to interpret the code above, but if someone could fix this to take care of all planar graphs, I could try to include it.
comment:8 followup: ↓ 9 Changed 5 years ago by
Fixing it to work for all plane graphs is not that simple. The problem lies not so much with this code as with the support for plane graphs in Sage. At the moment plane multigraphs are not supported, and I guess that also plane graphs with loops are not supported.
If the input graph is not 3edgeconnected, then the dual will not be a simple plane graph, so no code will work for those graphs until we first add support for plane multigraphs and plane graphs with loops.
comment:9 in reply to: ↑ 8 Changed 5 years ago by
If the input graph is not 3edgeconnected, then the dual will not be a simple plane graph, so no code will work for those graphs until we first add support for plane multigraphs and plane graphs with loops.
Ah, I see! Thanks for explaining the issue. Can we write a program to check for 3edgeconnectedness? If that is not too hard, then we can at least include the dual graph method for a large class of graphs (and many that other people are interested in). For graphs which fail that test, we can leave a NotImplemented
error. Does that seem doable?
comment:10 Changed 5 years ago by
That is certainly doable, since that is already implemented. (At least I think so) At the moment I'm a bit swamped with work, but I'll have a look at it after next week. feel free to poke me if I forget it, or to have a look at it yourself.
comment:11 Changed 5 years ago by
But I just checked before writing the previous message! There's no G.is_3_edge_connected()
or G.is_three_edge_connected()
or anything of that nature when I type G.is
and hit <tab>. Is there another equivalent definition? I'll look if so.
comment:12 Changed 5 years ago by
No, but there is a G.edge_connectivity()
, so just use that and check that it is at least 3. Probably something more efficient is possible when we just want to know whether it is at least 3, but for now you can just use that.
comment:13 Changed 5 years ago by
Great, thanks! I'll use that. Should I create a new branch and add it to the graph methods in graph.py? What is a class of planar examples which are 3edgeconnected? I thought of grid graphs, but they fail. :(
comment:14 Changed 5 years ago by
The Platonic solids are 3edgeconnected. You need to have graphs with minimum degree at least 3, because otherwise deleting the edges incident to a vertex of minimum degree will disconnect the graph. Also have a look at the methods added by #16970.
Creating a new branch and adding to the graph methods seems the best approach. Be sure to read the developers guide.
comment:15 Changed 2 years ago by
 Status changed from new to needs_info
Meanwhile there is a function .faces
for graphs. Therefore it would be quite straightforward to implement the planar dual; something along the lines of :
def planar_dual(P): return Graph([[tuple(_) for _ in P.faces()], lambda f,g: len(find_intersection(f,g))==1])
Therefore my question: Is this ticket really still open or has it been implemented elsewhere?
comment:16 Changed 2 years ago by
I'm not aware of any such code in sagemath. So go for it.
There are trivial speedup improvements for the .faces
method that I can implement in another ticket if you agree.
comment:17 Changed 2 years ago by
Some speedup improvements are implemented in #23630. It also raises questions regarding the expected output when the graph has a single vertex and for disconnected graphs. It might impact the planar_dual
method.
comment:18 Changed 2 years ago by
 Branch set to u/moritz/planar_dual
comment:19 Changed 2 years ago by
 Commit set to 2cb05c7ab29da97b5876da8f088f74bd1ecf68dc
 Status changed from needs_info to needs_review
I added the method, avoiding the potential difficulties with multiedges etc, by requiring the graph to be 3connected. (Better to have it in these cases than nothing...)
New commits:
2cb05c7  introduced planar_dual method

comment:20 Changed 2 years ago by
Why are you asking for 3edgeconnectivity ? If it's to prevent graphs with a cutvertex, the requirement is not sufficient and actually the method is apparently working in this case.
sage: G = graphs.IcosahedralGraph()*2 sage: G.merge_vertices([0,12]) sage: G.planar_dual() Graph on 39 vertices
We cannot get the dual of a 2d grid or a cycle.
We really need a proper implementation of the decomposition into 3 connected components, or an interface with OGDF
since it has a fast (and surely the only) implementation of the linear time algorithm.
comment:21 Changed 2 years ago by
Sorry, I got "edgeconnected" confused with "vertexconnected"
comment:22 Changed 2 years ago by
 Commit changed from 2cb05c7ab29da97b5876da8f088f74bd1ecf68dc to d7cea7f3ed773406d5bc8a8f9f6c46be483bb326
Branch pushed to git repo; I updated commit sha1. New commits:
d7cea7f  changed 'edge' to 'vertex'

comment:23 followup: ↓ 25 Changed 2 years ago by
Why 3 ? With 2vertexconnected we could get the dual of cycles, grids, etc.
Please change:
Finding the planar_dual is only works if the graph is at least 3 vertexconnected
>the graph must be at least 3vertexconnected
comment:24 Changed 2 years ago by
 Commit changed from d7cea7f3ed773406d5bc8a8f9f6c46be483bb326 to 356d3ac0ac1d3287223711c2e6c22e3000d39e4f
Branch pushed to git repo; I updated commit sha1. New commits:
356d3ac  typo: 3vertex

comment:25 in reply to: ↑ 23 Changed 2 years ago by
Replying to dcoudert:
Why 3 ? With 2vertexconnected we could get the dual of cycles, grids, etc.
Because then the dual will potentially have multiple edges. Take a square as an example: the dual graph has two vertices with 4 parallel edges.
Please change:
Finding the planar_dual is only works if the graph is at least 3 vertexconnected
>the graph must be at least 3vertexconnected
done
comment:26 Changed 2 years ago by
 Commit changed from 356d3ac0ac1d3287223711c2e6c22e3000d39e4f to 2468289d698ba9681e9a45511b63af9899274c35
Branch pushed to git repo; I updated commit sha1. New commits:
2468289  two more doctest and some pepcleaning

comment:27 Changed 2 years ago by
Some comments:
 add method
planar_dual
in thePlot/embeddingrelated methods
table at the top of the file Return the planar dual an embedded graph.
>Return the planar dual of an embedded graph.
? if a graph is 4vertexconnected, then it is also 3vertexconnected. So you don't need to specify
at least 3vertexconnected
.  the
SEEALSO
block must be after theEXAMPLES
block for g in [_ for _ in graphs.planar_graphs(i, minimum_connectivity=3)]
>for g in graphs.planar_graphs(i, minimum_connectivity=3)
 In fact, the tests using
graphs.planar_graphs
are nice but unduly time consuming. Add 2 sec for the doctests ofgeneric_graph.py
on my laptop. This is too much. You should use simpler / faster tests.  in the
TODO
block. You can simply write:Implement the method for graphs that are not 3vertexconnected (or at least have a faster 3vertexconnectivity test)
.  Usually, we use
from sage.graphs.graph import Graph
and notfrom . import graph
. You should do the same  you have not corrected the not implemented message
comment:28 Changed 2 years ago by
 Commit changed from 2468289d698ba9681e9a45511b63af9899274c35 to 922b58b454a8c4af6758b7d4b149b629209cb469
Branch pushed to git repo; I updated commit sha1. New commits:
922b58b  improvements form 'some comments'

comment:29 Changed 2 years ago by
Thanks for the comments, David!
I tried to work in the suggested imrovements.
First I had tried to put from sage.graphs.graph import Graph
in the top of the file, where all the imports are made, but this failed, due to circular imports.
comment:30 Changed 2 years ago by
 Reviewers set to David Coudert
 Status changed from needs_review to positive_review
For me this ticket is good to go (tests, docbuild and display ok, etc.)
comment:31 Changed 2 years ago by
Not sure if you inted to merge this, but without milestone it won't...
comment:33 Changed 2 years ago by
 Branch changed from u/moritz/planar_dual to 922b58b454a8c4af6758b7d4b149b629209cb469
 Resolution set to fixed
 Status changed from positive_review to closed
just in case sagenb.org goes down, here is the code: