Search

In this paper, we show a polynomial-time algorithm for testing c -planarity of embedded flat clustered graphs with at most two vertices per cluster on each face. Our result is based on a reduction to the planar set of spanning trees in topological multigraphs (pssttm) problem, which is defined as follows. Given a (non-planar) topological multigraph A with k connected components A 1 , ... , A k , do spanning trees of A 1 , ... , A k exist such that no two edges in any two spanning trees cross? Kratochvíl et al. [SIAM Journal on Discrete Mathematics, 4(2): 223–244, 1991] proved that the problem is NP-hard even if k = 1 ; on the other hand, Di Battista and Frati presented a linear-time algorithm to solve the pssttm problem for the case in which A is a 1 -planar topological multigraph [Journal of Graph Algorithms and Applications, 13(3): 349–378, 2009]. For any embedded flat clustered graph C , an instance A of the pssttm problem can be constructed in polynomial time such that C is c -planar if and only if A admits a solution. We show that, if C has at most two vertices per cluster on each face, then it can be tested in polynomial time whether the corresponding instance A of the pssttm problem is positive or negative. Our strategy for solving the pssttm problem on A is to repeatedly perform a sequence of tests, which might let us conclude that A is a negative instance, and simplifications, which might let us simplify A by removing or contracting some edges. Most of these tests and simplifications are performed "locally", by looking at the crossings involving a single edge or face of a connected component A i of A ; however, some tests and simplifications have to consider certain global structures in A , which we call α -donuts. If no test concludes that A is a negative instance of the pssttm problem, then the simplifications eventually transform A into an equivalent 1 -planar topological multigraph on which we can apply the cited linear-time algorithm by Di Battista and Frati. [ABSTRACT FROM AUTHOR]