Details

Exact algorithms for clustered planarity with linear saturators
ID Da Lozzo, Giordano (Author), ID Ganian, Robert (Author), ID Gupta, Siddharth (Author), ID Mohar, Bojan (Author), ID Ordyniak, Sebastian (Author), ID Zehavi, Meirav (Author)

URLURL - Source URL, Visit https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.24 This link opens in a new window
.pdfPDF - Presentation file, Download (1,10 MB)
MD5: 886974E83E4D5C48017633A20FCE0250

Abstract
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.

Language:English
Keywords:clustered planarity, independent c-graphs, path saturation, graph drawing
Work type:Article
Typology:1.08 - Published Scientific Conference Contribution
Organization:FMF - Faculty of Mathematics and Physics
Publication status:Published
Publication version:Version of Record
Year:2024
Number of pages:16 str.
PID:20.500.12556/RUL-176500 This link opens in a new window
UDC:004.42:519.17
DOI:10.4230/LIPIcs.ISAAC.2024.24 This link opens in a new window
COBISS.SI-ID:217948419 This link opens in a new window
Publication date in RUL:02.12.2025
Views:429
Downloads:199
Metadata:XML DC-XML DC-RDF
:
Copy citation
Share:Bookmark and Share

Record is a part of a monograph

Title:35th International Symposium on Algorithms and Computation : ISAAC 2024, December 8–11, 2024, Sydney, Australia
Editors:Julián Mestre, Anthony Wirth
Place of publishing:Saarbrücken/Wadern
Publisher:Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
Year:2024
ISBN:978-3-95977-354-6
COBISS.SI-ID:217939971 This link opens in a new window
Collection title:Leibniz international proceedings in informatics
Collection numbering:ǂvol. ǂ322
Collection ISSN:1868-8969

Licences

License:CC BY 4.0, Creative Commons Attribution 4.0 International
Link:http://creativecommons.org/licenses/by/4.0/
Description:This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.

Projects

Funder:MUR - Italian Ministry for Universities and Research
Funding programme:PRIN Project
Project number:2022ME9Z78 - NextGRAAL

Funder:MUR - Italian Ministry for Universities and Research
Funding programme:PRIN Project
Project number:2022TS4Y3N - EXPAND

Funder:FWF - Austrian Science Fund
Project number:10.55776/Y1329

Funder:WWTF - Vienna Science and Technology Fund
Project number:10.47379/ICT22029

Funder:Other - Other funder or multiple funders
Funding programme:BITS Pilani New Faculty Seed Grant

Funder:NSERC - Natural Sciences and Engineering Research Council of Canada
Funding programme:Discovery Grant
Project number:R832714

Funder:EC - European Commission
Project number:101071836
Name:KARST: Predicting flow and transport in complex Karst systems
Acronym:KARST

Funder:ARIS - Slovenian Research and Innovation Agency
Project number:N1-0218
Name:Prepletanje geometrije, topologije in algebre v strukturni in topološki teoriji grafov

Funder:EC - European Commission
Name:PARAPATH: Parameterized Complexity Through the Lens of Path Problems
Acronym:PARAPATH

Similar documents

Similar works from RUL:
Similar works from other Slovenian collections:

Back