4 papers
Finding Geometric Representations of Apex Graphs is NP-Hard
Dibyayan Chakraborty, Kshitij Gajjar
Planar graphs can be represented as intersection graphs of different types of geometric objects in the plane, e.g., circles (Koebe, 1936), line segments (Chalopin \& Gon{ç}alves, 2…
Generalized Parametric Path Problems
Prerona Chatterjee, Kshitij Gajjar, Jaikumar Radhakrishnan +1
Parametric path problems arise independently in diverse domains, ranging from transportation to finance, where they are studied under various assumptions. We formulate a general pa…
Parametric Shortest Paths in Planar Graphs
Kshitij Gajjar, Jaikumar Radhakrishnan
We construct a family of planar graphs , where has vertices including a source vertex and a sink vertex , and edge weights that change linearly…
Minimizing Branching Vertices in Distance-preserving Subgraphs
Kshitij Gajjar, Jaikumar Radhakrishnan
It is -hard to determine the minimum number of branching vertices needed in a single-source distance-preserving subgraph of an undirected graph. We show that this prob…