一种非平面图平面化的算法 [英] Algorithm for the Planarization of a non-planar Graph

问题描述

我目前正计划在Boost中为无向图实现正交平面布局算法（Boost Graph Library）。 BGL有一个实现来检查无向图的平面性（Boyer-Myrvold Planarity Testing），并且我打算使用这个方法返回的平面嵌入来做一个正交布局。

但是我不知道如果输入图是非平面的，应该做什么。我应该在这种情况下使用返回的Kuratowski子图做些什么来使图平面化。

关于非平面图的平面化的Google搜索会返回多个调查报告。我不确定从哪里开始。

解决方案

有许多$ K_5 $和$ K_ {3,3} $ $ K_n $的子图，不介意未成年人，所以直接对待他们并不是非常有效。我建议翻阅这些研究论文，以便了解其他人如何解决这个问题。您应该注意以下特性：（a）给出明智的解决方案，（b）听起来像您感兴趣的图表。

Is there a popular algorithm for the planarization of a non-planar graph.

I'm currently planning to implement a Orthogonal Planar Layout algorithm for undirected graphs in Boost ( Boost Graph Library ). BGL has an implementation to check the planarity of an undirected graph ( Boyer-Myrvold Planarity Testing ) and I plan to use the planar embedding returned by this method to do an orthogonal layout.

But I'm not sure what should be done if the input graph is non-planar. Should I do something with the Kuratowski sub-graph returned in such a scenario to make the graph planar.

A Google Search on "Planarization of non-planar graphs" returns multiple research papers. I'm not sure where to start.

解决方案

There are exponentially many $K_5$ and $K_{3,3}$ subgraphs of a $K_n$, never mind minors, so treating them directly isn't terribly efficient. I suggest flipping through said research papers to learn a bit about how other people approach the problem. You should pay attention to properties that (a) give sensible solutions and (b) sound like graphs that interest you.

这篇关于一种非平面图平面化的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！