19 citations · 37 across the 32 of their papers we have counts for
29 papers · 1 filter
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…
Quantum Speedup for Some Geometric 3SUM-Hard Problems and Beyond
J. Mark Keil, Fraser McLeod, Debajyoti Mondal
The classical 3SUM conjecture states that the class of 3SUM-hard problems does not admit a truly subquadratic -time algorithm, where , in classical computing. The…
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…
Finding a Maximum Clique in a Disk Graph
Jared Espenant, J. Mark Keil, Debajyoti Mondal
A disk graph is an intersection graph of disks in the Euclidean plane, where the disks correspond to the vertices of the graph and a pair of vertices are adjacent if and only if th…
Improved and Generalized Algorithms for Burning a Planar Point Set
Prashant Gokhale, J. Mark Keil, Debajyoti Mondal
Given a set of points in the plane, a point burning process is a discrete time process to burn all the points of where fires must be initiated at the given points. Specific…
Minimum Ply Covering of Points with Unit Squares
Stephane Durocher, J. Mark Keil, Debajyoti Mondal
Given a set of points and a set of axis-parallel unit squares in the Euclidean plane, a minimum ply cover of with is a subset of that covers and minimizes t…
Burning Number for the Points in the Plane
J. Mark Keil, Debajyoti Mondal, Ehsan Moradi
The burning process on a graph starts with a single burnt vertex, and at each subsequent step, burns the neighbors of the currently burnt vertices, as well as one other unburnt…
Bottleneck Convex Subsets: Finding Large Convex Sets in a Point Set
Stephane Durocher, J. Mark Keil, Saeed Mehrabi +1
Chvátal and Klincsek (1980) gave an -time algorithm for the problem of finding a maximum-cardinality convex subset of an arbitrary given set of points in the plane.…
Finding a Maximum Clique in a Grounded 1-Bend String Graph
J. Mark Keil, Debajyoti Mondal, Ehsan Moradi +1
A grounded 1-bend string graph is an intersection graph of a set of polygonal lines, each with one bend, such that the lines lie above a common horizontal line and have exac…
StreamTable: An Area Proportional Visualization for Tables with Flowing Streams
Jared Espenant, Debajyoti Mondal
Let be a two-dimensional table with each cell weighted by a nonzero positive number. A StreamTable visualization of represents the columns as non-overlapping vertical strea…
Simultaneous Embedding of Colored Graphs
Debajyoti Mondal
A set of colored graphs are compatible, if for every color , the number of vertices of color is the same in every graph. A simultaneous embedding of compatibly colored g…
Compatible Paths on Labelled Point Sets
Elena Arseneva, Yeganeh Bahoo, Ahmad Biniaz +8
Let and be finite point sets of the same cardinality in , each labelled from to . Two noncrossing geometric graphs and spanning and …
(Faster) Multi-Sided Boundary Labelling
Prosenjit Bose, Saeed Mehrabi, Debajyoti Mondal
A 1-bend boundary labelling problem consists of an axis-aligned rectangle , points (called sites) in the interior, and points (called ports) on the labels along the boun…
Parameterized Complexity of Two-Interval Pattern Problem
Prosenjit Bose, Saeed Mehrabi, Debajyoti Mondal
A \emph{2-interval} is the union of two disjoint intervals on the real line. Two 2-intervals and are \emph{disjoint} if their intersection is empty (i.e., no interval o…
Emanation Graph: A Plane Geometric Spanner with Steiner Points
Bardia Hamedmohseni, Zahed Rahmati, Debajyoti Mondal
An emanation graph of grade on a set of points is a plane spanner made by shooting equally spaced rays from each point, where the shorter rays stop the longer ones up…
Drawing HV-Restricted Planar Graphs
Stephane Durocher, Stefan Felsner, Saeed Mehrabi +1
A strict orthogonal drawing of a graph in is a drawing of such that each vertex is mapped to a distinct point and each edge is mapped to a horizontal…
Computing Maximum Independent Set on Outerstring Graphs and Their Relatives
Prosenjit Bose, Paz Carmi, J. Mark Keil +4
A graph with vertices is called an outerstring graph if it has an intersection representation of a set of curves inside a disk such that one endpoint of every curve is…
Polygon Simplification by Minimizing Convex Corners
Yeganeh Bahoo, Stephane Durocher, J. Mark Keil +3
Let be a polygon with reflex vertices and possibly with holes and islands. A subsuming polygon of is a polygon such that , each connected compone…
Recognition and Drawing of Stick Graphs
Felice De Luca, Md Iqbal Hossain, Stephen Kobourov +2
A \emph{Stick graph} is an intersection graph of axis-aligned segments such that the left end-points of the horizontal segments and the bottom end-points of the vertical segments l…
Boundary Labeling for Rectangular Diagrams
Prosenjit Bose, Paz Carmi, J. Mark Keil +2
Given a set of points (sites) inside a rectangle and points (label locations or ports) on its boundary, a boundary labeling problem seeks ways of connecting every site…
Angle-Monotone Graphs: Construction and Local Routing
Anna Lubiw, Debajyoti Mondal
A geometric graph in the plane is angle-monotone of width if every pair of vertices is connected by an angle-monotone path of width , a path such that the angles of any two…
A Note on Plus-Contacts, Rectangular Duals, and Box-Orthogonal Drawings
Therese Biedl, Debajyoti Mondal
A plus-contact representation of a planar graph is called -balanced if for every plus shape , the number of other plus shapes incident to each arm of is at most $…
On Upward Drawings of Trees on a Given Grid
Therese Biedl, Debajyoti Mondal
Computing a minimum-area planar straight-line drawing of a graph is known to be NP-hard for planar graphs, even when restricted to outerplanar graphs. However, the complexity quest…