Showing 2024Show all
3 papers · 1 filter
cs.DS2024
Dynamic parameterized problems on unit disk graphs
Shinwoo An, Kyungjin Cho, Leo Jang +6
In this paper, we study fundamental parameterized problems such as -Path/Cycle, Vertex Cover, Triangle Hitting Set, Feedback Vertex Set, and Cycle Packing for dynamic unit disk…
cs.CG2024
Sparse Outerstring Graphs Have Logarithmic Treewidth
Shinwoo An, Eunjin Oh, Jie Xue
An outerstring graph is the intersection graph of curves lying inside a disk with one endpoint on the boundary of the disk. We show that an outerstring graph with vertices has…
cs.DS2024
ETH-Tight Algorithm for Cycle Packing on Unit Disk Graphs
Shinwoo An, Eunjin Oh
In this paper, we consider the Cycle Packing problem on unit disk graphs defined as follows. Given a unit disk graph G with n vertices and an integer k, the goal is to find a set o…