Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Concept Videos

Vector Algebra: Graphical Method01:10

Vector Algebra: Graphical Method

12.8K
Vectors can be multiplied by scalars, added to other vectors, or subtracted from other vectors. The vector sum of two (or more) vectors is called the resultant vector or, for short, the resultant.
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...
12.8K
Coordination Number and Geometry02:57

Coordination Number and Geometry

16.5K
For transition metal complexes, the coordination number determines the geometry around the central metal ion. Table 1 compares coordination numbers to molecular geometry. The most common structures of the complexes in coordination compounds are octahedral, tetrahedral, and square planar.
16.5K
Castigliano's Theorem01:18

Castigliano's Theorem

475
Castigliano's theorem analyzes displacements and rotations in elastic structures. It relates the derivative of elastic strain energy to the applied forces or moments, allowing for the calculation of deformations. The theorem states that the partial derivative of the total strain energy of a system with respect to a specific load results in the displacement at the point where the load is applied. This principle applies to both forces and moments.
475
Lattice Centering and Coordination Number02:33

Lattice Centering and Coordination Number

9.8K
The structure of a crystalline solid, whether a metal or not, is best described by considering its simplest repeating unit, which is referred to as its unit cell. The unit cell consists of lattice points that represent the locations of atoms or ions. The entire structure then consists of this unit cell repeating in three dimensions. The three different types of unit cells present in the cubic lattice are illustrated in Figure 1.
Types of Unit Cells
Imagine taking a large number of identical...
9.8K
Second Uniqueness Theorem01:16

Second Uniqueness Theorem

1.1K
Consider a region consisting of several individual conductors with a definite charge density in the region between these conductors. The second uniqueness theorem states that if the total charge on each conductor and the charge density in the in-between region are known, then the electric field can be uniquely determined.
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...
1.1K
Electric Field of a Charged Disk01:23

Electric Field of a Charged Disk

2.3K
The simplest case of a surface charge distribution is the uniformly charged disk. Calculating its electric field also helps us calculate the electric field of a large plane of charge.
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...
2.3K

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same journal

Cover-free families on hypergraphs and combinatorial group testing.

Journal of combinatorial optimization·2026
Same journal

List 3-coloring on comb-convex and caterpillar-convex bipartite graphs.

Journal of combinatorial optimization·2026
Same journal

Agent-constrained truthful facility location games.

Journal of combinatorial optimization·2025
Same journal

Airline capacity distribution under financial budget and resource consideration.

Journal of combinatorial optimization·2023
Same journal

Target set selection in social networks with tiered influence and activation thresholds.

Journal of combinatorial optimization·2023
Same journal

Enhanced post-quantum key escrow system for supervised data conflict of interest based on consortium blockchain.

Journal of combinatorial optimization·2023

Related Experiment Video

Updated: Aug 25, 2025

ExCYT: A Graphical User Interface for Streamlining Analysis of High-Dimensional Cytometry Data
05:12

ExCYT: A Graphical User Interface for Streamlining Analysis of High-Dimensional Cytometry Data

Published on: January 16, 2019

11.5K

Computing a maximum clique in geometric superclasses of disk graphs.

Nicolas Grelier1

  • 1Department of Computer Science, ETH, Zürich, Switzerland.

Journal of Combinatorial Optimization
|October 19, 2022
PubMed
Summary

Researchers developed a polynomial time algorithm for the maximum clique problem on a geometric superclass of unit disk graphs, advancing computational geometry research. This work also provides partial results for an efficient polynomial time approximation scheme (EPTAS) for convex pseudo-disk intersection graphs.

Keywords:
Intersection graphsLine transversalsPseudo-disks

More Related Videos

Large-scale Reconstructions and Independent, Unbiased Clustering Based on Morphological Metrics to Classify Neurons in Selective Populations
12:27

Large-scale Reconstructions and Independent, Unbiased Clustering Based on Morphological Metrics to Classify Neurons in Selective Populations

Published on: February 15, 2017

7.0K
Detection of Architectural Distortion in Prior Mammograms via Analysis of Oriented Patterns
13:44

Detection of Architectural Distortion in Prior Mammograms via Analysis of Oriented Patterns

Published on: August 30, 2013

43.0K

Related Experiment Videos

Last Updated: Aug 25, 2025

ExCYT: A Graphical User Interface for Streamlining Analysis of High-Dimensional Cytometry Data
05:12

ExCYT: A Graphical User Interface for Streamlining Analysis of High-Dimensional Cytometry Data

Published on: January 16, 2019

11.5K
Large-scale Reconstructions and Independent, Unbiased Clustering Based on Morphological Metrics to Classify Neurons in Selective Populations
12:27

Large-scale Reconstructions and Independent, Unbiased Clustering Based on Morphological Metrics to Classify Neurons in Selective Populations

Published on: February 15, 2017

7.0K
Detection of Architectural Distortion in Prior Mammograms via Analysis of Oriented Patterns
13:44

Detection of Architectural Distortion in Prior Mammograms via Analysis of Oriented Patterns

Published on: August 30, 2013

43.0K

Area of Science:

  • Computational Geometry
  • Graph Theory
  • Algorithm Design

Background:

  • The maximum clique problem is polynomial time solvable for unit disk graphs (Clark et al., 1990s).
  • The problem is NP-hard for general ball graphs (Bonamy et al., FOCS '18).
  • An efficient polynomial time approximation scheme (EPTAS) exists for disk graphs.

Purpose of the Study:

  • To investigate the complexity of the maximum clique problem in geometric intersection graphs.
  • To develop a polynomial time algorithm for a superclass of unit disk graphs.
  • To advance towards an EPTAS for intersection graphs of convex pseudo-disks.

Main Methods:

  • Algorithmic analysis of geometric graph properties.
  • Exploration of graph superclasses related to unit disk graphs.
  • Development of approximation algorithms for intersection graphs.

Main Results:

  • Demonstrated the existence of a polynomial time algorithm for a geometric superclass of unit disk graphs.
  • Established new theoretical bounds and algorithmic possibilities for maximum clique on geometric intersection graphs.
  • Provided foundational results for achieving an EPTAS for convex pseudo-disk intersection graphs.

Conclusions:

  • The maximum clique problem remains tractable for certain geometric graph classes beyond unit disks.
  • Further research can build upon these results to develop approximation algorithms for complex geometric intersection graphs.
  • This work contributes to understanding the computational complexity of geometric optimization problems.