Shinwoo An

activity

20202026

collaborators

Showing cs.CGShow all

4 papers · 1 filter

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 $n$ vertices has…

cs.CG2023

Faster Algorithms for Cycle Hitting Problems on Disk Graphs

Shinwoo An, Kyungjin Cho, Eunjin Oh

In this paper, we consider three hitting problems on a disk intersection graph: Triangle Hitting Set, Feedback Vertex Set, and Odd Cycle Transversal. Given a disk intersection grap…

cs.CG2021

Feedback Vertex Set on Geometric Intersection Graphs

Shinwoo An, Eunjin Oh

In this paper, we present an algorithm for computing a feedback vertex set of a unit disk graph of size $k$ , if it exists, which runs in time $2^{O (k)} (n + m)$ , where $n$ and…

cs.CG2021

Reachability Problems for Transmission Graphs

Shinwoo An, Eunjin Oh

Let $P$ be a set of $n$ points in the plane where each point $p$ of $P$ is associated with a radius $r_{p} > 0$ .The transmission graph $G = (P, E)$ of $P$ is defined as the directed graph…