Homothetic polygons and beyond: maximal cliques in intersection graphs

DOI10.1016/J.DAM.2018.03.046zbMath1394.05106DBLPjournals/dam/BrimkovJKKPRST18OpenAlexW2796591137WikidataQ62595887 ScholiaQ62595887MaRDI QIDQ1671346

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

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

maximal cliquegeometric intersection graphs\(P_{h o m}\) graphs

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)

Related Items (3)

Intersection graphs of homothetic polygons ⋮ Unnamed Item ⋮ Maximal intersecting families and affine regular polygons in \(PG(2,q)\)

Uses Software

• CLIP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The clique problem in ray intersection graphs
• Fundamentals of parameterized complexity
• On the dimension of a face exposed by proper separation of convex polyhedra
• The worst-case time complexity for generating all maximal cliques and computational experiments
• Unit disk graphs
• Intersection graphs of segments
• On intersection representations of co-planar graphs
• Efficient graph representations
• The clique problem in intersection graphs of ellipses and triangles
• Algorithmic graph theory and perfect graphs
• The LBFS Structure and Recognition of Interval Graphs
• Convex Polygon Intersection Graphs
• On a Coloring Problem.
• Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
• Max-tolerance graphs as intersection graphs
• Arboricity and Subgraph Listing Algorithms
• A New Algorithm for Generating All the Maximal Independent Sets
• Topics in Intersection Graph Theory
• Robust algorithms for restricted domains
• Beyond Homothetic Polygons: Recognition and Maximum Clique
• On Intersection Graphs of Convex Polygons
• Integer Representations of Convex Polygon Intersection Graphs
• Intersection graphs of homothetic polygons
• Algorithm Theory - SWAT 2004
• Data reduction and exact algorithms for clique cover
• Parameterized Algorithms
• A Characterization of Comparability Graphs and of Interval Graphs
• On cliques in graphs

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