Homothetic polygons and beyond: maximal cliques in intersection graphs

DOI10.1016/J.DAM.2018.03.046MaRDI QIDQ1671346zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Valentin E. Brimkov, Konstanty Junosza-Szaniawski, Sean Kafer, Jan Kratochvíl, Martin Pergel, Paweł Rzążewski, Matthew Szczepankiewicz, Joshua Terhaar

Publication date 6 September 2018

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2018.03.046

zbMATH Keywords

\(P_{h o m}\) graphsgeometric intersection graphsmaximal clique

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph operations (line graphs, products, etc.) (05C76)

Recommendations

• Beyond homothetic polygons: recognition and maximum clique
• Intersection graphs of homothetic polygons
• On max-clique for intersection graphs of sets and the Hadwiger-Debrunner numbers
• On graphs whose maximal cliques and stable sets intersect
• A characterization of intersection graphs of the maximal rectangles of a polyomino
• Extremal graphs for intersecting cliques
• The clique problem in intersection graphs of ellipses and triangles
• On maximal cliques of polar graphs
• Maximum cliques of hypergraphs and polynomial optimization
• Intersection graphs of maximal hypercubes

Cites work

• A Characterization of Comparability Graphs and of Interval Graphs
• A New Algorithm for Generating All the Maximal Independent Sets
• Algorithm Theory - SWAT 2004
• Algorithmic graph theory and perfect graphs
• Arboricity and Subgraph Listing Algorithms
• Beyond homothetic polygons: recognition and maximum clique
• Convex Polygon Intersection Graphs
• Data reduction and exact algorithms for clique cover
• Efficient graph representations
• Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
• Fundamentals of parameterized complexity
• scientific article; zbMATH DE number 6118217 (Why is no real title available?)
• scientific article; zbMATH DE number 4200260 (Why is no real title available?)
• scientific article; zbMATH DE number 2145236 (Why is no real title available?)
• scientific article; zbMATH DE number 2117210 (Why is no real title available?)
• scientific article; zbMATH DE number 861332 (Why is no real title available?)
• scientific article; zbMATH DE number 3307331 (Why is no real title available?)
• Integer representations of convex polygon intersection graphs
• Intersection graphs of homothetic polygons
• Intersection graphs of segments
• Max-tolerance graphs as intersection graphs
• On a Coloring Problem.
• On cliques in graphs
• On intersection graphs of convex polygons
• On intersection representations of co-planar graphs
• On the dimension of a face exposed by proper separation of convex polyhedra
• Parameterized algorithms
• Robust algorithms for restricted domains
• State of the union (of geometric objects)
• The clique problem in intersection graphs of ellipses and triangles
• The clique problem in ray intersection graphs
• The LBFS structure and recognition of interval graphs
• The worst-case time complexity for generating all maximal cliques and computational experiments
• Topics in Intersection Graph Theory
• Unit disk graphs

Cited in

(10)

• Generalized octahedra and cliques in intersection graphs of uniform hypergraphs
• On the m-clique free interval subgraphs polytope: polyhedral analysis and applications
• Maximal intersecting families and affine regular polygons in PG(2,q)
• On max-clique for intersection graphs of sets and the Hadwiger-Debrunner numbers
• Beyond homothetic polygons: recognition and maximum clique
• QPTAS and subexponential algorithm for maximum clique on disk graphs
• On intersection graphs of convex polygons
• Intersection graphs of homothetic polygons
• Distinguishing classes of intersection graphs of homothets or similarities of two convex disks
• The maximum clique problem in a disk graph made easy

Describes a project that uses

Uses Software

• CLIP

This page was built for publication: Homothetic polygons and beyond: maximal cliques in intersection graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1671346)