find the dual graph of a planar graph

[jasongrout]

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.

CC: @sagetrac-brunellus @nvcleemp

Component: graph theory

Author: Moritz Firsching

Branch/Commit: 922b58b

Reviewer: David Coudert

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

[jasongrout]

comment:1

just in case sagenb.org goes down, here is the code:

def faces(g):
   d={}
   for key,val in g.get_embedding().iteritems():
       d[key]=dict(zip(val,val[1:]+[val[0]]))
   list_faces=[]
   for start in d:
       while d[start]:
           face=[]
           prev=start
           _,curr = d[start].popitem()
           face.append(start)
           while curr != start:
               face.append(curr)
               prev,curr = (curr, d[curr].pop(prev))
           list_faces.append(face)
   return list_faces

def graph_dual(g):
   f = [tuple(face) for face in faces(g)]
   f_edges = [tuple(zip(i,i[1:]+(i[0],))) for i in f]
   dual = Graph([f_edges,lambda f1,f2: set(f1).intersection([(e[1],e[0]) for e in f2])])
   return dual 

h=graphs.PathGraph(2)
g=h.disjoint_union(h).disjoint_union(h)
g=g.complement()
g.relabel()
show(g) 
        	

g.is_planar(set_embedding=True, set_pos=True)
show(g) 
        	

# The vertices forming the faces of the graph
faces(g) 
        	
dual_g=graph_dual(g) 
        	
# Each vertex is labeled with the edges of the face that it represents.
show(dual_g) 
        	

# We can relabel the vertices to get a "nice" graph, but then we lose the information about which face corresponds to which vertex.
dual_g.relabel()
show(dual_g) 

[loefflerd]

comment:2

This should be filed in "graph theory".

[nvcleemp]

comment:5

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 3-edge-connected simple planar graphs. Is this sufficient, or should we also try to make it work for other graphs? Supporting multigraphs might depend on #14657.

[jasongrout]

comment:6

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!

[ayyer]

comment:7

Hi,

I'm interested in this functionality too!

It seems that the code given as an example only 'works' for 3-edge-connected 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.

[nvcleemp]

comment:8

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 3-edge-connected, 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.

[ayyer]

comment:9

If the input graph is not 3-edge-connected, 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 3-edge-connectedness? 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?

[nvcleemp]

comment:10

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.

[ayyer]

comment:11

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 . Is there another equivalent definition? I'll look if so.

[nvcleemp]

comment:12

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.

[ayyer]

comment:13

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 3-edge-connected? I thought of grid graphs, but they fail. :(

[nvcleemp]

comment:14

The Platonic solids are 3-edge-connected. 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.

[mo271]

comment:15

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?

[dcoudert]

comment:16

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.

[dcoudert]

comment:17

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.

[mo271]

Branch: u/moritz/planar_dual

[mo271]

Commit: 2cb05c7

[mo271]

Author: Moritz Firsching

[mo271]

comment:19

I added the method, avoiding the potential difficulties with multi-edges etc, by requiring the graph to be 3-connected. (Better to have it in these cases than nothing...)

---

New commits:

2cb05c7

introduced planar_dual method

[dcoudert]

comment:20

Why are you asking for 3-edge-connectivity ? If it's to prevent graphs with a cut-vertex, 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.

[mo271]

comment:21

Sorry, I got "edge-connected" confused with "vertex-connected"

[sagetrac-git]

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

d7cea7f

changed 'edge' to 'vertex'

[sagetrac-git]

Changed commit from 2cb05c7 to d7cea7f

[dcoudert]

comment:23

Why 3 ? With 2-vertex-connected 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 vertex-connected -> the graph must be at least 3-vertex-connected

[sagetrac-git]

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

356d3ac

typo: 3-vertex

[sagetrac-git]

Changed commit from d7cea7f to 356d3ac

[mo271]

comment:25

Replying to @dcoudert:

Why 3 ? With 2-vertex-connected 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 vertex-connected -> the graph must be at least 3-vertex-connected

done

[sagetrac-git]

Changed commit from 356d3ac to 2468289

[sagetrac-git]

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

2468289

two more doctest and some pep-cleaning

[dcoudert]

comment:27

Some comments:

• add method planar_dual in the Plot/embedding-related 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 4-vertex-connected, then it is also 3-vertex-connected. So you don't need to specify at least 3-vertex-connected.
• the SEEALSO block must be after the EXAMPLES 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 of generic_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 3-vertex-connected (or at least have a faster 3-vertex-connectivity test).
• Usually, we use from sage.graphs.graph import Graph and not from . import graph. You should do the same
• you have not corrected the not implemented message

[sagetrac-git]

Changed commit from 2468289 to 922b58b

[sagetrac-git]

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

922b58b

improvements form 'some comments'

[mo271]

comment:29

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.

[dcoudert]

comment:30

For me this ticket is good to go (tests, docbuild and display ok, etc.)

[dcoudert]

Reviewer: David Coudert

[vbraun]

comment:31

Not sure if you inted to merge this, but without milestone it won't...

[dcoudert]

comment:32

Right. Thank you.

[vbraun]

Changed branch from u/moritz/planar_dual to 922b58b