Straight-line planar graph with maximum face and minimum depth

[Małgorzata Nowicka]

Hello!

I am trying to embed and draw a planar graph with straight lines, minimum depth and maximum face. Is it possible to use EmbedderMinDepthMaxFace with layouts other than orthogonal? 

In the paper introducing the embedder "Graph Embedding with Minimum Depth and Maximum External Face" by C. Gutwenger and P. Mutzel (2004), the authors refer only to orthogonal representation, but it is important for me for the graph to have no bends (setting the bendBound in OrthoLayout to zero doesn't make it). Trying the embedder with PlanarDrawLayout indeed produces a planar drawing but the size of the external face is not maximal and depth not minimal.

Thank you,

Małgorzata

[Dagobert Smart]

Dear Małgorzata,

the PlanarStraightLayout seems to work:

#include <ogdf/basic/graph_generators.h>
#include <ogdf/fileformats/GraphIO.h>
#include <ogdf/planarlayout/PlanarStraightLayout.h>
#include <ogdf/planarity/EmbedderMinDepthMaxFace.h>

using namespace ogdf;

int main()
{
    Graph G;
    randomPlanarBiconnectedGraph(G, 14, 20, false);
    GraphAttributes GA(G,
      GraphAttributes::nodeGraphics |
      GraphAttributes::edgeGraphics);

    for (node v : G.nodes) {
        GA.width(v) = 5;
        GA.height(v) = 5;
    }

    PlanarStraightLayout pl;
    EmbedderMinDepthMaxFace *emb = new EmbedderMinDepthMaxFace;
    pl.setEmbedder(emb);
    pl.call(GA);

    GraphIO::write(GA, "output.svg", GraphIO::drawSVG);

    return 0;
}

Best regards,
Dagobert

​

[Małgorzata Nowicka]

Thank you for your quick answer!

Indeed your example seems to be working. I tried the PlanarStraightLayout and am attaching a picture (couldn't figure out how to add a gml file to the message so here's a link: example.gml) of a graph that poses problems for me. Isn't the inner section supposed to be a part of the external face? 

After inspection, the OrthoLayout for the same graph also seems to produce a result that I can't understand (again, shouldn't the component inside the external face be on the outside?).

Am I misinterpreting what the embedder should be doing? If so, is there a way to achieve the characteristics (ie. colloquially no faces inside faces) another way?

Best,

Małgorzata

[Dagobert Smart]

I investigated this and it is indeed a bug, one that has been introduced in February 2017.
Moreover, I have an idea for a fix. In /include/ogdf/planarity/embedder/EmbedderBCTreeBase.h we have the following line 57:

EdgeArray<int> m_edgeLength(G, 0);

but it should actually be

EdgeArray<int> m_edgeLength(G, 1);

This might potentially break EmbedderMinDepth (I'm not sure about that yet) but for all other Embedders it might work fine. For the next release, we will take a closer at this but the fix might help you already.

Best regards,

Dagobert

​

[Małgorzata Nowicka]

Thank you so much for your help, the EmbedderMinDepthMaxFace works as expected now!

I have a follow up question in the same context to the PlanarStraightLayout/PlanarDrawLayout. Is the embedder embedding also the augmented edges that facilitate the planar drawing algorithm? This is what appears to me to happen (?) in the following graph: example.gml

Does it make sense to first embed the graph and only then augment it? Is there a way to do it?

Best,

Małgorzata

[Dagobert Smart]

Yes, the algorithm also embeds the augmenting edges.

Does it make sense to first embed the graph and only then augment it? Is there a way to do it?

The PlanarGridLayoutModules promise that they are able to what you want via callFixEmbed():

Graph G;
randomPlanarConnectedGraph(G, 20, 30);
GraphAttributes GA(G, GraphAttributes::all);
PlanarStraightLayout pl;

EmbedderMaxFace *emb = new EmbedderMaxFace;
adjEntry adjE;
emb->call(G, adjE);
pl.callFixEmbed(GA, adjE);

This, however, does not seem to work because the internally used PlanarAugmentationFix–which augments a graph while keeping the embedding–appears to be broken.
One could try to use a PlanarAugmentation instead of PlanarAugmentationFix (line 80 in PlanarStraightLayout.cpp), but since the PlanarAugmentation may not keep the original embedding, this will also break in many cases. Hence, I unfortunately can’t help you with this right now.

Best regards,
Dagobert

​

[Małgorzata Nowicka]

I see, thank you, you've been of great help!

Best,

Małgorzata