S. Mehrabi

activity

20132021

most citedApproximating Dominating Set on Intersection Graphs of Rectangles and L-frames

10 citations · 25 across the 18 of their papers we have counts for

collaborators

31 papers

cs.DS2021

Shortest Beer Path Queries in Outerplanar Graphs

Joyce Bacic, Saeed Mehrabi, Michiel Smid

A \emph{beer graph} is an undirected graph $G$ , in which each edge has a positive weight and some vertices have a beer store. A \emph{beer path} between two vertices $u$ and $v$ in…

cs.CG2021

Bottleneck Convex Subsets: Finding $k$ Large Convex Sets in a Point Set

Stephane Durocher, J. Mark Keil, Saeed Mehrabi +1

Chvátal and Klincsek (1980) gave an $O (n^{3})$ -time algorithm for the problem of finding a maximum-cardinality convex subset of an arbitrary given set $P$ of $n$ points in the plane.…

cs.CG2020

Upward Point Set Embeddings of Paths and Trees

Elena Arseneva, Pilar Cano, Linda Kleist +4

We study upward planar straight-line embeddings (UPSE) of directed trees on given point sets. The given point set $S$ has size at least the number of vertices in the tree. For the…

cs.CG2020★ 1 cited

(Faster) Multi-Sided Boundary Labelling

Prosenjit Bose, Saeed Mehrabi, Debajyoti Mondal

A 1-bend boundary labelling problem consists of an axis-aligned rectangle $B$ , $n$ points (called sites) in the interior, and $n$ points (called ports) on the labels along the boun…

cs.CG2020

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 $D_{1}$ and $D_{2}$ are \emph{disjoint} if their intersection is empty (i.e., no interval o…

cs.DM2019

Maximum Bipartite Subgraph of Geometric Intersection Graphs

Satyabrata Jana, Anil Maheshwari, Saeed Mehrabi +1

We study the Maximum Bipartite Subgraph (MBS) problem, which is defined as follows. Given a set $S$ of $n$ geometric objects in the plane, we want to compute a maximum-size subset…

cs.CG2019

Packing Boundary-Anchored Rectangles and Squares

Therese Biedl, Ahmad Biniaz, Anil Maheshwari +1

Consider a set $P$ of $n$ points on the boundary of an axis-aligned square $Q$ . We study the boundary-anchored packing problem on $P$ in which the goal is to find a set of interior…

cs.CG2019

Drawing HV-Restricted Planar Graphs

Stephane Durocher, Stefan Felsner, Saeed Mehrabi +1

A strict orthogonal drawing of a graph $G = (V, E)$ in $R^{2}$ is a drawing of $G$ such that each vertex is mapped to a distinct point and each edge is mapped to a horizontal…

cs.CG2019★ 1 cited

Constrained Orthogonal Segment Stabbing

Sayan Bandyapadhyay, Saeed Mehrabi

Let $S$ and $D$ each be a set of orthogonal line segments in the plane. A line segment $s \in S$ \emph{stabs} a line segment $s^{'} \in D$ if $s \cap s^{'} \neq = \emptyset$ . It is known that t…

cs.CG2019

Computing Maximum Independent Set on Outerstring Graphs and Their Relatives

Prosenjit Bose, Paz Carmi, J. Mark Keil +4

A graph $G$ with $n$ vertices is called an outerstring graph if it has an intersection representation of a set of $n$ curves inside a disk such that one endpoint of every curve is…

cs.CG2018

Evacuating Equilateral Triangles and Squares in the Face-to-Face Model

Huda Chuangpishit, Saeed Mehrabi, Lata Narayanan +1

Consider $k$ robots initially located at a point inside a region $T$ . Each robot can move anywhere in $T$ independently of other robots with maximum speed one. The goal of the robo…

cs.CG2018

Polygon Simplification by Minimizing Convex Corners

Yeganeh Bahoo, Stephane Durocher, J. Mark Keil +3

Let $P$ be a polygon with $r > 0$ reflex vertices and possibly with holes and islands. A subsuming polygon of $P$ is a polygon $P^{'}$ such that $P \subseteq P^{'}$ , each connected compone…

cs.CG2018

On the Minimum Consistent Subset Problem

Ahmad Biniaz, Sergio Cabello, Paz Carmi +4

Let $P$ be a set of $n$ colored points in the plane. Introduced by Hart (1968), a consistent subset of $P$ , is a set $S \subseteq P$ such that for every point $p$ in $P ∖ S$ ,…

cs.CG2018

Approximability of Covering Cells with Line Segments

Paz Carmi, Anil Maheshwari, Saeed Mehrabi +1

In COCOA 2015, Korman et al. studied the following geometric covering problem: given a set $S$ of $n$ line segments in the plane, find a minimum number of line segments such that e…

cs.CG2018

Boundary Labeling for Rectangular Diagrams

Prosenjit Bose, Paz Carmi, J. Mark Keil +2

Given a set of $n$ points (sites) inside a rectangle $R$ and $n$ points (label locations or ports) on its boundary, a boundary labeling problem seeks ways of connecting every site…

cs.CG2018

Geodesic Obstacle Representation of Graphs

Prosenjit Bose, Paz Carmi, Vida Dujmovic +4

An obstacle representation of a graph is a mapping of the vertices onto points in the plane and a set of connected regions of the plane (called obstacles) such that the straight-li…

cs.CG2018★ 10 cited

Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames

Sayan Bandyapadhyay, Anil Maheshwari, Saeed Mehrabi +1

We consider the Minimum Dominating Set (MDS) problem on the intersection graphs of geometric objects. Even for simple and widely-used geometric objects such as rectangles, no sub-l…

cs.DS2017

Approximating Weighted Duo-Preservation in Comparative Genomics

Saeed Mehrabi

Motivated by comparative genomics, Chen et al. [9] introduced the Maximum Duo-preservation String Mapping (MDSM) problem in which we are given two strings $s_{1}$ and $s_{2}$ from the…

cs.CG2017

Grid-Obstacle Representations with Connections to Staircase Guarding

Therese Biedl, Saeed Mehrabi

In this paper, we study grid-obstacle representations of graphs where we assign grid-points to vertices and define obstacles such that an edge exists if and only if an $x y$ -monoton…

cs.CG2017★ 1 cited

A Note on Approximating Weighted Independence on Intersection Graphs of Paths on a Grid

Saeed Mehrabi

A graph $G$ is called $B_{k}$ -VPG, for some constant $k \geq 0$ , if it has a string representation on an axis-parallel grid such that each vertex is a path with at most $k$ bends and…

cs.CG2017★ 1 cited

On Guarding Orthogonal Polygons with Bounded Treewidth

Therese Biedl, Saeed Mehrabi

There exist many variants of guarding an orthogonal polygon in an orthogonal fashion: sometimes a guard can see an entire rectangle, or along a staircase, or along an orthogonal pa…

cs.CG2017★ 4 cited

Approximation Algorithms for Independence and Domination on B $_{1}$ -VPG and B $_{1}$ -EPG Graphs

Saeed Mehrabi

A graph $G$ is called B $_{k}$ -VPG (resp., B $_{k}$ -EPG), for some constant $k \geq 0$ , if it has a string representation on a grid such that each vertex is an orthogonal path with at mos…

cs.CG2016★ 2 cited

1-Bend RAC Drawings of 1-Planar Graphs

Walter Didimo, Giuseppe Liotta, Saeed Mehrabi +1

A graph is 1-planar if it has a drawing where each edge is crossed at most once. A drawing is RAC (Right Angle Crossing) if the edges cross only at right angles. The relationships…

cs.CG2016

Unique Set Cover on Unit Disks and Unit Squares

Saeed Mehrabi

We study the Unique Set Cover problem on unit disks and unit squares. For a given set $P$ of $n$ points and a set $D$ of $m$ geometric objects both in the plane, the objective of t…

Shortest Beer Path Queries in Outerplanar Graphs

Bottleneck Convex Subsets: Finding k Large Convex Sets in a Point Set

Upward Point Set Embeddings of Paths and Trees

(Faster) Multi-Sided Boundary Labelling

Parameterized Complexity of Two-Interval Pattern Problem

Maximum Bipartite Subgraph of Geometric Intersection Graphs

Packing Boundary-Anchored Rectangles and Squares

Drawing HV-Restricted Planar Graphs

Constrained Orthogonal Segment Stabbing

Computing Maximum Independent Set on Outerstring Graphs and Their Relatives

Evacuating Equilateral Triangles and Squares in the Face-to-Face Model

Polygon Simplification by Minimizing Convex Corners

On the Minimum Consistent Subset Problem

Approximability of Covering Cells with Line Segments

Boundary Labeling for Rectangular Diagrams

Geodesic Obstacle Representation of Graphs

Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames

Approximating Weighted Duo-Preservation in Comparative Genomics

Grid-Obstacle Representations with Connections to Staircase Guarding

A Note on Approximating Weighted Independence on Intersection Graphs of Paths on a Grid

On Guarding Orthogonal Polygons with Bounded Treewidth

Approximation Algorithms for Independence and Domination on B1​-VPG and B1​-EPG Graphs

1-Bend RAC Drawings of 1-Planar Graphs

Unique Set Cover on Unit Disks and Unit Squares

Bottleneck Convex Subsets: Finding $k$ Large Convex Sets in a Point Set

Approximation Algorithms for Independence and Domination on B $_{1}$ -VPG and B $_{1}$ -EPG Graphs