Related Experiment Video
Updated: Aug 25, 2025

ExCYT: A Graphical User Interface for Streamlining Analysis of High-Dimensional Cytometry Data
Published on: January 16, 2019
Computing a maximum clique in geometric superclasses of disk graphs
1Department of Computer Science, ETH, Zürich, Switzerland.
Abstract:
In the 90's Clark, Colbourn and Johnson wrote a seminal paper where they proved that maximum clique can be solved in polynomial time in unit disk graphs. Since then, the complexity of maximum clique in intersection graphs of d-dimensional (unit) balls has been investigated. For ball graphs, the problem is NP-hard, as shown by Bonamy et al. (FOCS '18). They also gave an efficient polynomial time approximation scheme (EPTAS) for disk graphs. However, the complexity of maximum clique in this setting remains unknown. In this paper, we show the existence of a polynomial time algorithm for a geometric superclass of unit disk graphs. Moreover, we give partial results toward obtaining an EPTAS for intersection graphs of convex pseudo-disks.
More Related Videos
12:27Large-scale Reconstructions and Independent, Unbiased Clustering Based on Morphological Metrics to Classify Neurons in Selective Populations
Published on: February 15, 2017
13:44Detection of Architectural Distortion in Prior Mammograms via Analysis of Oriented Patterns
Published on: August 30, 2013
Related Concept Videos
Vector Algebra: Graphical Method
We use the laws of geometry to construct resultant vectors, followed by trigonometry to find vector magnitudes and directions. For a geometric construction of the sum of two vectors in a plane, we follow the parallelogram rule. Suppose two vectors are at arbitrary positions. Translate either one of...
Coordination Number and Geometry
Castigliano's Theorem
Lattice Centering and Coordination Number
Types of Unit Cells
Imagine taking a large number of identical...
Second Uniqueness Theorem
In contrast, consider that the electric field is non-unique and apply Gauss's law in divergence form in the region between the conductors and the integral form to the...
Electric Field of a Charged Disk
The system's symmetry is in the cylindrical directions across the plane of the charge. As a result, the electric fields created by various surface charge elements nullify each other in the direction parallel to the surface. Thereby, the resulting electric field is perpendicular to the plane. Since the disk is...