Speaker

Eunjin Oh

Title

How Geometry Changes the Computational Landscape

Abstract

Many fundamental graph problems are computationally hard on arbitrary inputs, but their complexity can change dramatically when the input carries geometric structure. This talk asks two questions: What geometric structures can graphs have, and why do those structures lead to faster algorithms? To address the first question, I will begin by examining three ways in which graphs can encode geometry: through crossing-free embeddings, through shortest-path distances that approximate Euclidean distances, and through intersections among geometric objects. These representations define distinct graph classes, and even small changes in the underlying geometric assumptions can lead to sharp changes in computational complexity. To address the second question, I will show that geometry can make algorithms faster by providing structures unavailable in general graphs. Clique-based separators decompose unit disk graphs into smaller subproblems, while compact representations avoid explicitly processing the quadratic-size graph underlying geometric multimatching. Taken together, these examples illustrate how geometry changes the computational landscape.

Bio

Eunjin Oh is an associate professor in the Department of Computer Science and Engineering at POSTECH. Her research bridges graph algorithms and computational geometry, with a focus on geometric optimization, shortest-path and distance problems in geometric graphs, and parameterized and approximation algorithms. She received her B.S. and Ph.D. in Computer Science and Engineering from POSTECH, completing her Ph.D. in 2018. After a postdoctoral fellowship at the Max Planck Institute for Informatics in Germany, she joined the POSTECH faculty in 2019 and became an associate professor in 2023. She currently serves as an editor for Theoretical Computer Science and the Journal of Computational Geometry and served as a program co-chair for WADS 2025.

Language

English (Offline)