True Contraction Decomposition and Almost Eth-Tight Bipartization for Unit-Disk Graphs

Authors

Sayan Bandyapadhyay, Portland State University
William Lochet, Université de Montpellier
Daniel Lokshtanov, University of California, Santa Barbara
Saket Saurabh, Institute of Mathematical Sciences
Jie Xue, New York University Shanghai

Published In

Acm Transactions on Algorithms

Document Type

Article

Publication Date

7-1-2024

Subjects

Computational geometry -- graphs

Abstract

We prove a structural theorem for unit-disk graphs, which (roughly) states that given a set D of n unit disks inducing a unit-disk graph ...

Rights

© 2024 Copyright held by the owner/author(s).

Locate the Document

https://doi.org/10.1145/3656042

DOI

10.1145/3656042

Persistent Identifier

https://archives.pdx.edu/ds/psu/42573

Citation Details

Bandyapadhyay, S., Lochet, W., Lokshtanov, D., Saurabh, S., & Xue, J. (2024). True Contraction Decomposition and Almost ETH-Tight Bipartization for Unit-Disk Graphs. ACM Transactions on Algorithms, 20(3), 1–26.