Efficient c-planarity testing algebraically
Radoslav Fulek, Jan Kynčl, Igor Malinović, Dömötör Pálvölgyi · arXiv (Cornell University) · 2013
Abstract. We generalize the strong Hanani-Tutte theorem to clustered graphs with two disjoint clusters, and show that an extension of our result to flat clustered graphs with three disjoint clusters is not possible. We also give a new and short proof for a result by Di Battista and Frati about efficient c-planarity testing of an embedded flat clustered graph with small faces based on the matroid intersection algorithm.