Publications
(In all the publications, the authors' names are listed alphabetically by last name)
Publications
(In all the publications, the authors' names are listed alphabetically by last name)
Research Interests
My research lies in the interface of Discrete Mathematics and Theoretical Computer Science, with a primary focus on graph theory and hypergraphs. I work on the structural and algorithmic aspects of (hyper)graphs with a particular emphasis on applications to packing, covering, and coloring problems. I am also strongly interested in combinatorics and discrete & computational geometry.
A short description of my research in hypergraphs: A central theme of my work on hypergraphs is the design of algorithms for the construction of sparse supports -- graphs on the vertices of the hypergraph ensuring that each hyperedge induces a connected subgraph. The existence of a sparse support implies applications to hypergraph coloring, and PTAS for generalized Packing and Covering problems using the local search framework. The notion also has connections to other domains, including hypergraph visualization and network design. I study these problems in geometric as well as abstract settings, aiming to understand how structural properties can be exploited to obtain combinatorial and geometric guarantees.
Supports for Outerplanar and Bounded Treewidth Graphs
R. Raman and K. Singh
[arXiv] (under review at Disc. Appl. Math.).
Ordered Yao Graphs: Maximum Degree, Edge Density, and Clique Numbers
P. Ágoston, A. Dumitrescu, A. Sagdeev, K. Singh, and J. Zeng
Computational Geometry: Theory and Applications
[CGTA] (2026).
Approximate sunflowers with convex sets
K. Elbassioni, R. Raman, S. Ray, and K. Singh
Discrete Mathematics
[DM] (2026)
On Supports for Graphs of Bounded Genus
R. Raman and K. Singh
[DMTCS] (2026)
Maximizing the Maximum Degree in Ordered Nearest Neighbor Graphs
P. Ágoston, A. Dumitrescu, A. Sagdeev, K. Singh, and J. Zeng
Computational Geometry: Theory and Applications
[CGTA] (2026)
The Complexity of Recognizing ABAB-free Hypergraphs
G. Damásdi, B. Keszegh, D. Pálvölgyi, and K. Singh
Discrete Mathematics and Theoretical Computer Science (Special issues of Permutation Patterns, 2024).
[DMTCS] (2025)
Ordered Yao Graphs: Maximum Degree, Edge Numbers, and Clique Numbers
P. Ágoston, A. Dumitrescu, A. Sagdeev, K. Singh, and J. Zeng
XXI Spanish Meeting on Computational Geometry.
[EGC] (2025)
Maximizing the Maximum Degree in Ordered Nearest Neighbor Graphs
P. Ágoston, A. Dumitrescu, A. Sagdeev, K. Singh, and J. Zeng
11th Annual International Conference on Algorithms and Discrete Applied Mathematics.
[CALDAM] (2025, Best Presentation Award).
A Fast Algorithm for Computing a Planar Support for Non-piercing Rectangles
A. Pal, R. Raman, S. Ray, and K. Singh
35th International Symposium on Algorithms and Computation.
[ISAAC] (2024)
Hypergraph Supports (abstract)
A. Pal, R. Raman, S. Ray, and K. Singh
SIAM Conference on Discrete Mathematics
[SIAM(DM)] (2024)
On Hypergraph Supports
R. Raman, K. Singh
European Conference on Combinatorics, Graph Theory and Applications.
[EUROCOMB] (2023)
Co-authors (not in any particular order)
Rajiv Raman (IIIT-Delhi), Dömötör Pálvölgyi (ELTE and Rényi Institute, Budapest), Gábor Damásdi (ELTE and Rényi Institute, Budapest), Balázs Keszegh (ELTE and Rényi Institute, Budapest), Adrian Dumitrescu (AlgOrEsEArch; Rényi Institute, Budapest, and ICUB Romania), Arsenii Sagdeev (KIT Germany), Ji Zeng (UCSD and Rényi Institute, Budapest), Péter Ágoston (ELTE and Rényi Institute, Budapest), Ambar Pal (Johns Hopkins Uni. USA), Saurabh Ray (NYU Abu Dhabi)
Academic Services
Reviewer/subreviewer: SoCG, CALDAM, and Communications in Combinatorics and Optimization.
Session Chair: SIAM-DM (24)