J. Keil

activity

20182024

collaborators

Showing cs.CGShow all

7 papers · 1 filter

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