Eunjin Oh

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