5 papers
Finding Cliques in Geometric Intersection Graphs with Grounded or Stabbed Constraints
J. Mark Keil, Debajyoti Mondal
A geometric intersection graph is constructed over a set of geometric objects, where each vertex represents a distinct object and an edge connects two vertices if and only if the c…
Computing Conforming Partitions with Low Stabbing Number for Rectilinear Polygons
Therese Biedl, Stephane Durocher, Debajyoti Mondal +2
A conforming partition of a rectilinear n-gon P (possibly with holes) is a partition of P into rectangles without using Steiner points (i.e., all corners of all rectangles must lie…
Subsetwise and Multi-Level Additive Spanners with Lightness Guarantees
Reyan Ahmed, Debajyoti Mondal, Rahnuma Islam Nishat
An \emph{additive + spanner} of an edge weighted graph is a subgraph of such that for every pair of vertices and , , wh…
The Maximum Clique Problem in a Disk Graph Made Easy
J. Mark Keil, Debajyoti Mondal
A disk graph is an intersection graph of disks in . Determining the computational complexity of finding a maximum clique in a disk graph is a long-standing open probl…
Improved Outerplanarity Bounds for Planar Graphs
Therese Biedl, Debajyoti Mondal
In this paper, we study the outerplanarity of planar graphs, i.e., the number of times that we must (in a planar embedding that we can initially freely choose) remove the outerface…