Abstract
For a clustered graph, i.e, a graph whose vertex set is recursively partitioned into clusters, the CPlanarity Testing problem asks whether it is possible to find a planar embedding of the graph and a representation of each cluster as a region homeomorphic to a closed disk such that 1. the subgraph induced by each cluster is drawn in the interior of the corresponding disk, 2. each edge intersects any disk at most once, and 3. the nesting between clusters is reflected by the representation, i.e., child clusters are properly contained in their parent cluster. The computational complexity of this problem, whose study has been central to the theory of graph visualization since its introduction in 1995 [Feng, Cohen, and Eades, Planarity for clustered graphs, ESA'95], has only been recently settled [Fulek and Tóth, Atomic Embeddability, Clustered Planarity, and Thickenability, to appear at SODA'20]. Before such a breakthrough, the complexity question was still unsolved even when the graph has a prescribed planar embedding, i.e, for embedded clustered graphs.
We show that the CPlanarity Testing problem admits a singleexponential singleparameter FPT algorithm for embedded clustered graphs, when parameterized by the carvingwidth of the dual graph of the input. This is the first FPT algorithm for this longstanding open problem with respect to a single notable graphwidth parameter. Moreover, in the general case, the polynomial dependency of our FPT algorithm is smaller than the one of the algorithm by Fulek and Tóth. To further strengthen the relevance of this result, we show that the CPlanarity Testing problem retains its computational complexity when parameterized by several other graphwidth parameters, which may potentially lead to faster algorithms.
BibTeX  Entry
@InProceedings{dalozzo_et_al:LIPIcs:2019:11470,
author = {Giordano Da Lozzo and David Eppstein and Michael T. Goodrich and Siddharth Gupta},
title = {{CPlanarity Testing of Embedded Clustered Graphs with Bounded Dual CarvingWidth}},
booktitle = {14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
pages = {9:19:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771290},
ISSN = {18688969},
year = {2019},
volume = {148},
editor = {Bart M. P. Jansen and Jan Arne Telle},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11470},
URN = {urn:nbn:de:0030drops114705},
doi = {10.4230/LIPIcs.IPEC.2019.9},
annote = {Keywords: Clustered planarity, carvingwidth, noncrossing partitions, FPT}
}
Keywords: 

Clustered planarity, carvingwidth, noncrossing partitions, FPT 
Collection: 

14th International Symposium on Parameterized and Exact Computation (IPEC 2019) 
Issue Date: 

2019 
Date of publication: 

04.12.2019 