<div class="csl-bib-body">
<div class="csl-entry">Depian, T., Dobler, A., Wulms, J., & Kern, C. (2024). Minimizing Corners in Colored Rectilinear Grids. In <i>WALCOM: Algorithms and Computation - 18th International Conference and Workshops on Algorithms and Computation, WALCOM 2024, Kanazawa, Japan, March 18–20, 2024, Proceedings</i> (pp. 134–148). Springer, Singapore.</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/203884
-
dc.description.abstract
Given a rectilinear grid G, in which cells are either assigned a single color, out of k possible colors, or remain white, can we color white grid cells of G to minimize the total number of corners of the resulting colored rectilinear polygons in G? We show how this problem relates to hypergraph visualization, prove that it is NP-hard even for k = 2, and present an exact dynamic programming algorithm. Together with a set of simple kernelization rules, this leads to an FPT-algorithm in the number of colored cells of the input. We additionally provide an XP-algorithm in the solution size, and a polynomial O (OP T)-approximation algorithm.
en
dc.language.iso
en
-
dc.subject
shape complexity
en
dc.subject
rectilinear polygons
en
dc.subject
set visualization
en
dc.title
Minimizing Corners in Colored Rectilinear Grids
en
dc.type
Inproceedings
en
dc.type
Konferenzbeitrag
de
dc.description.startpage
134
-
dc.description.endpage
148
-
dc.type.category
Full-Paper Contribution
-
tuw.booktitle
WALCOM: Algorithms and Computation - 18th International Conference and Workshops on Algorithms and Computation, WALCOM 2024, Kanazawa, Japan, March 18–20, 2024, Proceedings
-
tuw.container.volume
14549
-
tuw.peerreviewed
true
-
tuw.book.ispartofseries
Lecture Notes in Computer Science
-
tuw.relation.publisher
Springer, Singapore
-
tuw.researchTopic.id
I1
-
tuw.researchTopic.name
Logic and Computation
-
tuw.researchTopic.value
100
-
tuw.publication.orgunit
E192 - Institut für Logic and Computation
-
dc.description.numberOfPages
15
-
tuw.author.orcid
0009-0003-7498-6271
-
tuw.author.orcid
0000-0002-0712-9726
-
tuw.event.name
18th International Conference and Workshops on Algorithms and Computation, WALCOM 2024)
en
tuw.event.startdate
18-03-2024
-
tuw.event.enddate
20-03-2024
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Kanazawa
-
tuw.event.country
JP
-
tuw.event.presenter
Depian, Thomas
-
wb.sciencebranch
Informatik
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.oefos
1010
-
wb.sciencebranch.value
80
-
wb.sciencebranch.value
20
-
item.languageiso639-1
en
-
item.openairetype
conference paper
-
item.grantfulltext
none
-
item.fulltext
no Fulltext
-
item.cerifentitytype
Publications
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
-
crisitem.author.dept
E192-02 - Forschungsbereich Databases and Artificial Intelligence
