J. Keil

activity

20182024

collaborators

11 papers

cs.CG2024

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 $R^{2}$ . Determining the computational complexity of finding a maximum clique in a disk graph is a long-standing open probl…

cs.CG2023

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…

cs.CG2022

Improved and Generalized Algorithms for Burning a Planar Point Set

Prashant Gokhale, J. Mark Keil, Debajyoti Mondal

Given a set $P$ of points in the plane, a point burning process is a discrete time process to burn all the points of $P$ where fires must be initiated at the given points. Specific…

cs.CG2022

Minimum Ply Covering of Points with Unit Squares

Stephane Durocher, J. Mark Keil, Debajyoti Mondal

Given a set $P$ of points and a set $U$ of axis-parallel unit squares in the Euclidean plane, a minimum ply cover of $P$ with $U$ is a subset of $U$ that covers $P$ and minimizes t…

cs.CG2022

Burning Number for the Points in the Plane

J. Mark Keil, Debajyoti Mondal, Ehsan Moradi

The burning process on a graph $G$ 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…

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.CG2021

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…

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

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

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.DS2018

Swapping Colored Tokens on Graphs

Katsuhisa Yamanaka, Takashi Horiyama, J. Mark Keil +5

We investigate the computational complexity of the following problem. We are given a graph in which each vertex has an initial and a target color. Each pair of adjacent vertices ca…

The Maximum Clique Problem in a Disk Graph Made Easy

Finding a Maximum Clique in a Disk Graph

Improved and Generalized Algorithms for Burning a Planar Point Set

Minimum Ply Covering of Points with Unit Squares

Burning Number for the Points in the Plane

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

Finding a Maximum Clique in a Grounded 1-Bend String Graph

Computing Maximum Independent Set on Outerstring Graphs and Their Relatives

Polygon Simplification by Minimizing Convex Corners

Boundary Labeling for Rectangular Diagrams

Swapping Colored Tokens on Graphs

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