maximal planar subgraph

[peter robbins]

Hello,

I am interested in computing a maximal planar subgraph of an undirected (ideally weighted) graph. The page https://ogdf.uos.de/doc/group__ga-plansub.html lists several algorithms for this. Unfortunately, I am new to OGDF, and I don't understand how to use these classes. Could somebody give a running example on how to run, say, Chalermsook/Schmid approximation algorithm for a given weighted graph? OGDF/test/src/planarity/planar-subgraph.cpp shows some example, but I am having a hard time following it. I could run the example at https://ogdf.uos.de/doc/ex-basic.html, "Planarizing a graph", but it was not obvious to me how modify it for the task described above.

Thank you,

Peter.

[Dagobert Smart]

Hello Peter,

the “Planarizing a graph” section does not actually help you as it computes a planarization, i.e. a planar representation of a graph with crossings replaced by degree-4-vertices (it only uses a planar subgraph algorithm as a subroutine). Here’s a planar subgraph example instead.

#include <ogdf/basic/graph_generators.h>
#include <ogdf/planarity/PlanarSubgraphTriangles.h>
#include <ogdf/planarity/MaximalPlanarSubgraphSimple.h>
#include <ogdf/fileformats/GraphIO.h>
#include <ogdf/energybased/FMMMLayout.h>

using namespace ogdf;

int main()
{
        Graph G;
        // First create the graph.
        // You can either read in a graph from a file using GraphIO:
        GraphAttributes GA(G, GraphAttributes::edgeDoubleWeight);
        GraphIO::read(GA, G, "mygraph.gml", GraphIO::readGML);
        // Or you use a graph generator, e.g.
        //   randomBiconnectedGraph(G, 42, 100);
        // If you have a specific small graph in mind, you can use the customGraph generator:
        //   customGraph(G, 5, {{0,1}, {0,2}, {0,3}, {0,4}, {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}});

        // Transfer weights from GraphAttributes to an EdgeArray.
        // If you did not read your graph from a file that includes the edge
        // weights, you would have to set the weights manually.
        EdgeArray<double> weights(G);
        for (edge e : G.edges) {
                weights[e] = GA.doubleWeight(e);
        }

        // Algorithm call.
        // The wrapper MaximalPlanarSubgraphSimple naively extends the planar
        // subgraph to an inclusion-wise one.
        List<edge> delEdges;
        PlanarSubgraphTriangles<double> ps;
        MaximalPlanarSubgraphSimple<double> alg(ps);
        alg.call(G, weights, delEdges);
        // delEdges now has those edges that have to be deleted to create planar subgraph.

        // Now you could just delete the edges and write the graph again.
        // for (edge e : delEdges) {
        //         G.delEdge(e);
        // }
        // GraphIO::write(GA, "planar-subgraph.gml", GraphIO::writeGML);

        // Here is some visual output instead:
        GA.addAttributes(GraphAttributes::nodeLabel |
                        GraphAttributes::nodeGraphics |
                        GraphAttributes::nodeStyle |
                        GraphAttributes::edgeGraphics |
                        GraphAttributes::edgeStyle);
        for (node v : G.nodes) {
                GA.label(v) = std::to_string(v->index());
                GA.width(v) = GA.height(v) = 20.0;
        }

        for (edge e : delEdges) {
                GA.strokeColor(e) = Color::Name::Red;
                GA.strokeType(e) = StrokeType::Dash;
        }

        FMMMLayout fmmm;
        fmmm.call(GA);
        GA.scale(2.0, false);

        GraphIO::write(GA, "planar-subgraph.gml", GraphIO::writeGML);
        GraphIO::write(GA, "planar-subgraph.svg", GraphIO::drawSVG);

        return 0;
}

I hope this helps you.

Best regards,
Dagobert

​

[peter robbins]

Great, thanks a lot for fast reply!

May I also ask whether the following algorithm is supported:

go through edges in a specified order and add a given edge only if this preserves planarity.

(This would be one way to force certain edges in the subgraph).

Thanks,

Peter,

PS. I tried replacing

PlanarSubgraphTriangles<double> ps;

with

      PlanarSubgraphEmpty<double> ps;

in your code. According to the description of ogdf::MaximalPlanarSubgraphSimple< TCost, typename std::enable_if< std::is_integral< TCost >::value >::type > ,

this would implement a similar greedy procedure. Only it looks like that the edges are processed not in the order in which they were added: when adding graph K_5,

the removed edge is not necessarily the last one.

[Dagobert Smart]

Hello Peter,

you’re correct, as far as I know, using a PlanarSubgraphEmpty<double> as a basis for the MaximalPlanarSubgraphSimple<double> is currently the closest algorithm we have to what you are searching for.
(The PlanarSubgraphModule also seems to have a parameter preferredEdges but that parameter is currently ignored in seemingly all implementations.)

In general, there is no guarantee on the order of vertices or edges in graph.nodes or graph.edges. E.g., if you use a GraphIO::read function, it may add edges to a graph completely unrelated to the order of these edges in the respective file. However, even though there is officially no guarantee, most functions make no changes to the order of edges in the graph, so there might still be a way to accomplish what you want.
I noticed the following: In line 257-260 of MaximalPlanarSubgraphSimple.h, the edges are ordered according to their weight + some randomness (based on the normalizedCosts computed in lines 241-249, for MaximalPlanarSubgraphSimple<int> see line 115). Maybe you can try to comment out those lines. If you do not use a file reader that changes the edge order, this may already help you.

Best regards,
Dagobert

​