A Quasi-Polynomial Time Algorithm for 3-Coloring Circle Graphs
Ajaykrishnan E S, Robert Ganian, Daniel Lokshtanov, and Vaishali Surianarayanan
图G是一个圆图,如果它是一个单位圆的和弦的交叉图。 我们给出一个算法,它以输入一个n顶点圆图G,在最多n^O(log n)时运行,并找到一个适当的3色G,如果存在的话。 因此,我们获得了具有相同运行时间的算法,以确定给定的有序图形(G,≺)是否具有3页的书嵌入。 这就部分解决了众所周知的Dujmović和Wood[Disc雷特]的公开问题。 数学。 原。 计算。 科幻。 2004年],Eppstein [2014],和Bachmann,Rutter和Stumpf [J. Graph Algorithms 应用。 2024] 圆图上的3色是否承认多项式时间算法。
A graph G is a circle graph if it is an intersection graph of chords of a unit circle. We give an algorithm that takes as input an n vertex circle graph G, runs in time at most n^O(log n) and finds a proper 3-coloring of G, if one exists. As a consequence we obtain an algorithm with the same running time to determine whether a given ordered graph (G, ≺) has a 3-page book embedding. This gives a partial resolution to the well known open problem of Dujmović and Wood [Discret. Math. Theor. Comput. ...
