We present computational results of an implementation based on the fixed parameter tractability (FPT) approach for biplanariz-ing graphs. These results show that the implementation can efficiently minimum biplanarizing sets containing up to about 18 edges, thus making it comparable to previous integer linear programming approaches. We show how our implementation slightly improves the theoretical running time to O(6~(bpr_(G))+ |G|). Finally, we explain how our experimental work predicts how performance on sparse graphs may be improved.
展开▼
机译:我们介绍了基于固定参数可处理性(FPT)方法的双图图形实现的计算结果。这些结果表明,该实现可以有效地最小化包含多达约18条边的双平面化集,从而使其可与以前的整数线性规划方法相提并论。我们展示了我们的实现如何将理论运行时间稍微提高到O(6〜(bpr_(G))+ | G |)。最后,我们解释了我们的实验工作如何预测稀疏图的性能可能会得到改善。
展开▼