Eunjin Oh
Associate Professor
Dept. of Computer Science and Engineering
Pohang University of Science and Technology (POSTECH)
I am an associate professor at the Department of Computer Science and Engineering, POSTECH. Before joining POSTECH, I was a postdoctoral fellow at Max Planck Institute for Informatics, hosted by Kurt Mehlhorn. I completed my Ph.D. from POSTECH in 2018.
My research interests lie in algorithms, data structures, and computational geometry. More specifically, I am interested in shortest path problems in simple polygons, point location problems, and dynamic data structures for geometric objects.
Personal: My husband also works at POSTECH.
Selected Publications
(A complete list can be found here)
Approximation Algorithms for the Geometric Multimatching Problem, STOC 2025 (with Shinwoo An and Jie Xue)
Pre-assignment problem for unique minimum vertex cover on bounded clique-width graphs, AAAI 2025 (with Shinwoo An, Yeonsu Chang, Kyungjin Cho, O-joung Kwon, Myounghwan Lee, and Hyeonjun Shin)
Mimicking Networks for Constrained Multicuts in Hypergraphs, ISAAC 2024 (with Kyungjin Cho)
Dynamic Parameterized Problems on Unit Disk Graphs, ISAAC 2024 (with Shinwoo An, Kyungjin Cho, Leo Jang, Byeonghyeon Jung, Yudam Lee, Donghun Shin, Hyeonjun Shin, and Chanho Song)
Sparse Outerstring Graphs Have Logarithmic Treewidth, ESA 2024 (with Shinwoo An and Jie Xue)
ETH-Tight Algorithm for Cycle Packing on Unit Disk Graphs, SoCG 2024 (with Shinwoo An)
Optimal Algorithm for the Planar Two-Center Problem, SoCG 2024 (with Kyungjin Cho, Haitao Wang and Jie Xue)
Approximate Distance and Shortest-Path Oracles for Fault-Tolerant Geometric Spanners. AAAI 2024 (with Kyungjin Cho and Jihun Shin)
Algorithms for Computing Maximum Cliques in Hyperbolic Random Graphs, ESA 2023 (with Seunghyeok Oh)
Faster Algorithms for Cycle Hitting Problems on Disk Graphs, WADS 2023 (with Shinwoo An and Kyungjin Cho)
Parameterized Algorithms for the Planar Disjoint Paths Problem: Exponential in k^2 and Linear in n, SODA 2023 (with Kyungjin Cho and Seunghyeok Oh)
The Maximum-Level Vertex in an Arrangement of Lines, Discrete & Computational Geometry. (with Dan Halperin, Sariel Har-Peled, Kurt Mehlhorn, Micha Sharir)
Linear-Time Approximation Scheme for k-Means Clustering of Axis-Parallel Affine Subspaces. ISAAC 2021 (with Kyungjin Cho)
Feedback Vertex Set in Unit Disk Graphs, ISAAC 2021 (with Shinwoo An)
Reachability Oracles in Geometric Tranmission Graphs. WADS 2021 and Algorithmica (with Shinwoo An)
Shortest Path Queries in Geometric Networks. ISAAC 2020
Optimal Algorithm for Geodesic Nearest-point Voronoi Diagrams. SODA 2019
Minimizing Distance-to-Sight in Polygonal Domains, ISAAC 2018
Point Location in Incremental Planar Subdivisions. ISAAC 2018
Approximate range clustering queries, SoCG 2018. (with Hee-Kap Ahn)
Point location in dynamic planar subdivisions. SoCG 2018. (with Hee-Kap Ahn)
Dynamic geodesic convex hulls in dynamic simple polygons, SoCG 2017. (with Hee-Kap Ahn)
Voronoi diagrams for a moderate-sized point-set in a simple polygon, SoCG 2017. (with Hee-Kap Ahn)
The farthest-point geodesic Voronoi diagram for points on the boundary of a simple polygon, SoCG 2016. (with Luis Barba and Hee-Kap Ahn)
A linear-time algorithm for the geodesic center of a simple polygon, SoCG 2015 and Discrete & Computational Geometry. (with Hee-Kap Ahn, Luis Barba, Prosenjit Bose, Jean-Lou de Carufel, Matias Korman)
Academic Activities
Program co-chair of WADS'25
Program chair of CG:YRF'25
Co-organizer of Dagstuhl Seminar: Computational Geometry 2025
Program committee member of SoCG 2025, ISAAC 2025, IPEC 2025, ISAAC 2024, ISAAC 2023, ESA 2023, SOSA 2023, WAOA 2022, MFCS 2021, CG:YRF 21, SoCG 20, EuroCG19
Contact
Office: Room 229, Building 2,
77 Cheongam-Ro, Nam-Gu, Pohang, Gyeongbuk, Republic of Korea, ZIP: 37673
Email: eunjin.oh@postech.ac.kr
Phone: (+82) 054-279-2389