标签: planar-graph

生成大型(~300k顶点)随机平面图的最有效方法是什么("随机"在这里意味着均匀分布)？

我正在学习平面图和c ++着色.但我不知道安装算法来做这项工作.有人请帮帮我？

在这里,我有一些信息给你!这是我的代码!它仍然有一个功能没有完成.如果有人知道什么是"平面图",请修复下面的Planar_Graph函数!:D非常感谢!:X

# define MAX 100

int kt[MAX];
int tk=0;

int my_array[MAX][MAX];      // Graph
FILE *f;
int n,m;            //m: Edge, n: Vertex
int index[MAX];            
int ke[MAX];      
int Color[MAX]   ;      //Color Array
int colors_max;      
char filename[MAX];

int input(char filename[MAX])   
{
    int i,j;

    f = fopen(filename,"r");
    if (f== NULL)
    {
        printf("\n Error \n");
        return 1;
    }
    else
    {
        printf("File mane: %s \n",filename);
        printf("Content   :\n");
        fscanf(f,"%d",&n);
        fscanf(f,"%d",&m);

        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            {
                fscanf(f,"%d",&my_array[i][j]);
                printf("%d   ",my_array[i][j]);
            }
            printf("\n");
        }      
        return 0;
    }   
}

void …

在布置图表时,有哪些边缘重叠最小化技术？(最好与GraphViz相关)还有哪些现有的软件能够以平面方式布局图形？

当前布局 - http://www.evecakes.com/doodles/master.gif

左上角的粉红色部分看起来很好,而浅蓝色部分有一些可避免的边缘重叠.

在绘制不相关的图形时,我遇到了以下算法问题:

我们有一个二分图的平面绘图,其中不相交的集合按列排列,如图所示.我们如何重新排列每列中的节点,以便最小化边缘交叉的数量？我知道这个问题对于一般图形(链接)来说是NP难的,但考虑到图形是二分的,是否存在一些技巧？

作为后续,如果有第三列w,只有v的边缘怎么办？还是进一步？

我有一个几何无向平面图,这是一个图,其中每个节点都有一个位置,没有2个边交叉,我想找到没有边穿过它们的所有周期.

这个问题有没有什么好的解决方案？

我打算做的是一种A*类似的解决方案:

• 将最小堆中的每个边插入路径
• 每个选项都可以扩展最短路径
• 循环回到其他路径的剔除路径(可能不需要)
• 剔除路径,这将是第三个使用ang给定边缘的路径

有没有人看到这个问题？它会工作吗？

我正在使用networkx(一个python图形绘图包)http://networkx.lanl.gov/index.html进行我的一个项目.虽然networkx非常酷,但由于交叉边缘的数量,显示功能很糟糕.有没有办法最小化图中的交叉边？我的意思是一种算法,它可以以一种最小化交叉边缘的方式对节点进行排序？

我遇到了许多可以表示为图形问题的问题.它通常是NP难的,但有时可以证明图是平面的.因此,我有兴趣学习这些问题和算法.

据我所知:

1. 最大切割平面图
2. 平面图中的四色
3. 立方平面图中的最大独立集

希望有人可以填写此列表.

我有相对较小的(40-80个节点)立方(3-regular)平面图,我必须决定它们的汉密尔顿性.我知道这个任务是NP完全的,但我希望渐近指数时间算法对我感兴趣的图形大小来说非常快.

出于本文的目的,通过平面图或平面图,我将表示可以在平面中(或等效地在球体上)绘制的抽象图,以及每个顶点处的边的圆形顺序.特定的这种绘图.这些额外信息决定了球体上的嵌入(直到移动顶点和边缘,使得它们永远不会与任何其他顶点/边相交).我不希望让循环和多重边.

例如,假设我们已经构建了如下图形.在平面中绘制两个顶点(A和B),以及连接这两个顶点的两条边.两个边缘一起形成一个简单的闭合曲线\ gamma.现在再添加两个顶点A'和B',并用边连接A和A',B和B'连接.

根据顶点A'和B'是否由曲线\ gamma分开,这个抽象图将具有两个不等价的嵌入.

我的问题是:是否有一个Python包实现了这样的平面图？

我感兴趣的是一个包可以创建平面图的绘图(当然,尊重嵌入),以及执行一些标准操作(例如给出面数,形成双图等)

如果Python中不存在这样的包,我也会对其他语言的实现感兴趣.

当然,有各种包实现图形绘制和图形理论算法.但是,我没有注意到任何一种已经嵌入嵌入式图形的可能性.非常感谢参考.

编辑.让我再详细说明一下.如果球体与其自身的同胚相关,则球体中相同图形的两个嵌入是等效的.正如上面提到的,平面图形的嵌入是不是唯一的,在一般情况下,所以我是问不相同,以测试平面图形和绘图一些其嵌入.

有几种组合方式可以将嵌入编码到这种等效性.可能最简单的是在每个顶点记录边缘的循环次序("旋转系统"),但还有许多其他的.有关讨论和参考,请参阅维基百科上有关图嵌入的文章.

人们可能希望对这种组合嵌入进行明显的操作,例如找到图的面,找到边/顶点相邻的面,在面上插入顶点,细分边,绘制图片嵌入等

是否有一个或几个这些数据结构的实现表示Python中可用的组合图嵌入？(我注意到图形嵌入在一般表面上是有意义的,尽管我主要对球体的情况感兴趣.)

我有两组n个节点.现在我想将一组中的每个节点与另一组中的另一个节点连接起来.结果图应该没有交叉点.

我知道几种扫描线算法(Bentley-Ottmann-Algorithm来检查交叉点发生的位置,但除了蛮力方法之外,我找不到解决这些交叉点的​​算法.

一组中的每个节点可以连接到另一组中的任何其他节点.

任何解决这个问题的(一种有效的)算法的指针？无需实施.

编辑1:

以下是该问题的一种解决方案n=7:

黑点是一组节点,红点是一组.每个黑色节点必须连接到一个红色节点,以便连接它们的线不交叉.

EDIT2:

为了进一步说明:所有节点的位置都是固定的,结果图将有n个边.我也没有任何证据证明存在解决方案,但我无法创建一个没有解决方案的例子.我确信在那里有一个证据可以创建这样一个平面图.此外,只需要一种解决方案,而不是所有可能的解决方案.