Your browser does not allow JavaScript!
JavaScript is necessary for the proper functioning of this website. Please enable JavaScript or use a modern browser.
Repository of the University of Ljubljana
Open Science Slovenia
Open Science
DiKUL
slv
|
eng
Search
Advanced
New in RUL
About RUL
In numbers
Help
Sign in
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
)
URL - Source URL, Visit
https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.24
PDF - Presentation file,
Download
(1,10 MB)
MD5: 886974E83E4D5C48017633A20FCE0250
Image galllery
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
UDC:
004.42:519.17
DOI:
10.4230/LIPIcs.ISAAC.2024.24
COBISS.SI-ID:
217948419
Publication date in RUL:
02.12.2025
Views:
429
Downloads:
199
Metadata:
Cite this work
Plain text
BibTeX
EndNote XML
EndNote/Refer
RIS
ABNT
ACM Ref
AMA
APA
Chicago 17th Author-Date
Harvard
IEEE
ISO 690
MLA
Vancouver
:
Copy citation
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
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