20.500.12556/RUL-176500 Exact algorithms for clustered planarity with linear saturators We study Clustered Planarity with Linear Saturators, which is the problem of augmenting an $n$-vertex planar graph whose vertices are partitioned into independent sets (called clusters) with paths - one for each cluster - that connect all the vertices in each cluster while maintaining planarity. We show that the problem can be solved in time $2^{{\mathcal O}(n)}$ for both the variable and fixed embedding case. Moreover, we show that it can be solved in subexponential time $2^{{\mathcal O}(\sqrt{n} \log n)}$ in the fixed embedding case if additionally the input graph is connected. The latter time complexity is tight under the Exponential-Time Hypothesis. We also show that $n$ can be replaced with the vertex cover number of the input graph by providing a linear (resp. polynomial) kernel for the variable-embedding (resp. fixed-embedding) case; these results contrast the NP-hardness of the problem on graphs of bounded treewidth (and even on trees). Finally, we complement known lower bounds for the problem by showing that Clustered Planarity with Linear Saturators is NP-hard even when the number of clusters is at most $3$, thus excluding the algorithmic use of the number of clusters as a parameter. clustered planarity independent c-graphs path saturation graph drawing true false true Angleški jezik Angleški jezik Članek v reviji 2025-12-02 13:33:06 2025-12-02 13:33:10 2025-12-22 03:53:46 0000-00-00 00:00:00 2024 0 0 16 str. 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 004.42:519.17 10.4230/LIPIcs.ISAAC.2024.24 217948419 217939971 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.24 1 ae0061b8-cf7a-11f0-9328-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=222866 LIPIcs.ISAAC.2024.24_(1).pdf LIPIcs.ISAAC.2024.24_(1).pdf 1 886974E83E4D5C48017633A20FCE0250 a698fcc477a2e87609e0c03745f814be6f934e7dd0e6f8d49ca27c41dbc5c8b3 caddecc9-cf7c-11f0-9328-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=222871 Fakulteta za matematiko in fiziko 0 0 0