In this paper, we study the Planar Disjoint Paths problem: Given an undirected planar graph with n vertices and a set of k pairs of vertices, the goal is to find a set k pairwise vertex-disjoint paths connecting each pairs. 

We present an FPT-algorithm for the Planar Disjoint Paths problem which takes linear time depends on n and single exponential time depends on k. This improves the two previously best-known algorithms: linear in n time but double exponential in k  time algorithm [Discrete Applied Mathematics 1995] and single exponential in k  but n  to the 6 time algorithm [STOC 2020].

Given an undirected graph, the FVS(Feedback Vertex Set) problem asks for finding a minimum number of vertices whose removal makes the graph acyclic. We study this problem on unit disk graphs (UDGs). Disks in the plane forms a vertices of UDG, and two vertices are connected by an edge of UDG if their corresponding disks are intersect each other.

The FVS problem is NP-hard, but in the parametrized complexity theory, we analyze the running time of an algorithm with respect to the input size and a new parameter. Here, we use the solution size as a parameter.

In this work, we present  an ETH-Tight algorithm for the FVS problem on unit disk graphs. In other words, if there is an algorithm faster than our algorithm, it disobeys ETH hypothesis, which is a stronger version of  P!=NP hypothesis.

Geometric random graphs can be models for many real-world graphs. In this work, we focus on hyperbolic random graphs. A hyperbolic random graph can be considered as a mathematical model for analyzing scale-free networks since it effectively explains the power-law degree distribution of scale-free networks. 

Using randomness and geometrical properties, various algorithms can be improved using average-case analysis. In this work, we present efficient algorithms for computing a maximum clique problem. We evaluate the performance of our algorithm theoretically and practically.

In this work, we study approximate distance oracles for fault-tolerant geometric graphs. Given a geometric graph G, our goal is to design a data structure using linear space so that, given two query vertices and a set of failed vertices, an approximate distance between the two query vertices avoiding the failed vertices can be computed efficiently. 

In general, no data structure for this problem using subquadratic space exists. In this work, using geometric tools, we presented a data structure for this problem on geometric graphs using near-linear space.