Dynamic Planarity Test

[Shangdi Yu]

Hello!

I am trying to do the following:

Starting with a planar graph G, I want to test if adding an edge e keeps G planar. If so, add the edge. If not, not add the edge. 

I'm wondering what's the most efficient way to do this in OGDF? Do I have to create a new graph {G +e} from scratch and test if it is planar? i.e. is there any dynamic/incremental planarity testing in OGDF? 

It seems that VariableEmbeddingInserter might serve my purpose, but I am not sure how to use it. Any help would be much appreciated. 

Thanks!

Best,

Shangdi 

[Dagobert Smart]

Hello Shangdi,

the normal planarity test already runs in linear time, so it should usually suffice. In fact, that’s roughly how e.g. MaximalPlanarSubgraphSimple works–it always tests whether adding an edge would make it non-planar. Maybe that class already does everything you want? If not, here's the general idea of how to go about it:

edge e = G.addEdge(v, w);
if (!isPlanar(G)) {
    G.delEdge(e);
}

The VariableEmbeddingInserter gives you a crossing minimum planarization of G+e (with G planar) such that all crossings lie on the edge e. So you could just check afterwards whether there are any crossings on e; if not, G+e is planar.
However, this method also needs linear time because it builds up an SPQR-tree of the whole graph. In fact, in practice this construction might take more time than the normal planarity test.
We also have VariableEmbeddingInserterDyn which uses a dynamic SPQR-tree but that only helps when inserting multiple edges at once.

VariableEmbeddingInserter inserter;
Graph G;
...

for (...) {
    edge e = G.newEdge(v,w);
    PlanRepLight pr{G};
    Array<edge> insertEdges({e});

    inserter.call(pr, insertEdges);
    if (pr.chain(e).size() > 1) {
        // e is split up into more than one edge segment (-> has crossing)
        G.delEdge(e);
    }
}

Best regards,
Dagobert

​

[Shangdi Yu]

Hi Dagobert,

Thank you very much for your help! In fact what I want is similar to the MaximalPlanarSubgraphSimple you mentioned. I want to test the edges in some order one by one, and only add it if it does not violate planarity.  

I have three more following questions. 

1. 

Why do we need to re-create "PlanRepLight pr{G};" in every for-loop? Is it because we cannot delete the edge from "pr" if we add the wrong edge? I think there is a way to test whether adding an edge violates planarity using the dynamic SPQR-tree without changing the dynamic SPQR-tree structure, is there such a functionality in OGDF?

2. I have the following code, does it look right? Specifically, I'm not sure if this is the correct way to add new edges to G. The newEdge function only accept node type, but I'm not sure how to obtain the node with a specific index from the graph.

```

// init edge_list with edges in some order

  Graph G;

Array<node> nodes(n);

for(int i=0; i< n; ++i){

nodes[i] = G.newNode(i);

}

for(std::pair<int, int> ep : edge_list){

edge e = G.newEdge(nodes[ep.first], nodes[ep.second]);

if (!isPlanar(G)) {

G.delEdge(e);

}

}

``` 

3. I tried the following code as well, but it seg faults. Do you know what might be wrong here?

(I cannot do PlanRepLight pr{G}; because of "no matching constructor for initialization")

```

  Graph G;

VariableEmbeddingInserter inserter;

Array<node> nodes(n);

for(int i=0; i< n; ++i){

nodes[i] = G.newNode(i);

}

edge e = G.newEdge(nodes[0], nodes[1]);

PlanRep PRG = PlanRep(G);

PlanRepLight pr{PRG};

Array<edge> insertEdges({e});

inserter.call(pr, insertEdges); //segfaults at this line

```

Sorry for the long message and thank you very much for your help!

Best,

Shangdi 

[Dagobert Smart]

Hello Shangdi,

1). Yes, you can use the same PlanRepLight in every loop with:

prl.removeEdgePath(origEdge);

or, if you use a CombinatorialEmbedding in some way:

prl.removeEdgePathEmbedded(myCombinatorialEmbedding, origEdge);

I think you are right and there is a way to do the planarity check using a (dynamic) SPQR-tree, but I don’t think we have this exact functionality in the OGDF (maybe the VariableEmbeddingInserter does this implicitly).

2). Yes, looks right. This is the way to do it (since v->index() should generally not be used in user code).

3). Oh, I forgot a stupid quirk of PlanRep(Light):

PlanRepLight prl {pr};
prl.initCC(0); // As long as your graph is connected, this should work.

Best regards,
Dagobert

​

[Shangdi Yu]

Hi Dagobert,

Thanks for your help!  For "prl.initCC(0);", if my graph is not connected, I suppose I need to do this once for each CC? Is there an easy way to loop over all CC's in a PlanRep(Light) graph or a Graph? 

Best,

Shangdi

[Dagobert Smart]

Hello Shangdi,

you can do a for-loop up to prl.numberOfCCs() - 1, see https://ogdf.github.io/doc/ogdf/classogdf_1_1_plan_rep_light.html

Best regards,
Dagobert

​