research
∙
10/29/2021
Shortest Beer Path Queries in Outerplanar Graphs
A beer graph is an undirected graph G, in which each edge has a positive...
share
research
∙
08/27/2021
Bottleneck Convex Subsets: Finding k Large Convex Sets in a Point Set
Chvátal and Klincsek (1980) gave an O(n^3)-time algorithm for the proble...
research
∙
12/18/2020
Upward Point Set Embeddings of Paths and Trees
We study upward planar straight-line embeddings (UPSE) of directed trees...
research
∙
02/22/2020
(Faster) Multi-Sided Boundary Labelling
A 1-bend boundary labelling problem consists of an axis-aligned rectangl...
research
∙
02/12/2020
Parameterized Complexity of Two-Interval Pattern Problem
A 2-interval is the union of two disjoint intervals on the real line. Tw...
research
∙
09/09/2019
Maximum Bipartite Subgraph of Geometric Intersection Graphs
We study the Maximum Bipartite Subgraph(MBS) problem, which is defined a...
research
∙
06/27/2019
Packing Boundary-Anchored Rectangles and Squares
Consider a set P of n points on the boundary of an axis-aligned square Q...
research
∙
04/30/2019
Constrained Orthogonal Segment Stabbing
Let S and D each be a set of orthogonal line segments in the plane. A li...
research
∙
04/14/2019
Drawing HV-Restricted Planar Graphs
A strict orthogonal drawing of a graph G=(V, E) in R^2 is a drawing of G...
research
∙
03/17/2019
Computing Maximum Independent Set on Outerstring Graphs and Their Relatives
A graph G with n vertices is called an outerstring graph if it has an in...
research
∙
12/25/2018
Evacuating Equilateral Triangles and Squares in the Face-to-Face Model
Consider k robots initially located at a point inside a region T. Each r...
research
∙
12/13/2018
Polygon Simplification by Minimizing Convex Corners
Let P be a polygon with r>0 reflex vertices and possibly with holes and ...
research
∙
10/22/2018
On the Minimum Consistent Subset Problem
Let P be a set of n colored points in the plane. Introduced by Hart (196...
research
∙
09/26/2018
Approximability of Covering Cells with Line Segments
In COCOA 2015, Korman et al. studied the following geometric covering pr...
research
∙
03/28/2018
Boundary Labeling for Rectangular Diagrams
Given a set of n points (sites) inside a rectangle R and n points (label...
research
∙
03/16/2018
Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames
We consider the Minimum Dominating Set (MDS) problem on the intersection...
research
∙
03/16/2018
Approximating Dominating Set on Intersection Graphs of L-frames
We consider the Dominating Set (DS) problem on the intersection graphs o...
research
∙
03/09/2018
Geodesic Obstacle Representation of Graphs
An obstacle representation of a graph is a mapping of the vertices onto ...
research
∙
08/30/2017
A Note on Approximating Weighted Independence on Intersection Graphs of Paths on a Grid
A graph G is called B_k-VPG, for some constant k≥ 0, if it has a string ...
research
∙
08/06/2017
Grid-Obstacle Representations with Connections to Staircase Guarding
In this paper, we study grid-obstacle representations of graphs where we...
research
∙
06/07/2017