Exact algorithms for clustered planarity with linear saturators

Da Lozzo, Giordano (avtor), Ganian, Robert (avtor), Gupta, Siddharth (avtor), Mohar, Bojan (avtor), Ordyniak, Sebastian (avtor), Zehavi, Meirav (avtor)

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.

• Jezik: Angleški jezik
• Ključne besede: clustered planarity, independent c-graphs, path saturation, graph drawing
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.08 - Objavljeni znanstveni prispevek na konferenci
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Leto izida: 2024
• Št. strani: 16 str.
• PID: 20.500.12556/RUL-176500
• UDK: 004.42:519.17
• DOI: 10.4230/LIPIcs.ISAAC.2024.24
• COBISS.SI-ID: 217948419
• Datum objave v RUL: 02.12.2025

Gradivo je del monografije

• Naslov: 35th International Symposium on Algorithms and Computation : ISAAC 2024, December 8–11, 2024, Sydney, Australia
• Uredniki: Julián Mestre, Anthony Wirth
• Kraj izida: Saarbrücken/Wadern
• Založnik: Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
• Leto izida: 2024
• ISBN: 978-3-95977-354-6
• COBISS.SI-ID: 217939971
• Naslov zbirke: Leibniz international proceedings in informatics
• Številčenje v zbirki: ǂvol. ǂ322
• ISSN zbirke: 1868-8969

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.