Max-tolerance graphs as intersection graphs

DOI10.1145/1109557.1109649zbMath1192.05102OpenAlexW4237681658MaRDI QIDQ3581555

Michael Kaufmann, Jan Kratochvíl, Amarendran R. Subramanian, Katharina A. Zweig

Publication date: 16 August 2010

Published in: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1109557.1109649

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (13)

Intersection graphs of homothetic polygons ⋮ Max point-tolerance graphs ⋮ Homothetic polygons and beyond: maximal cliques in intersection graphs ⋮ Computing list homomorphisms in geometric intersection graphs ⋮ Co-bipartite neighborhood edge elimination orderings ⋮ A \textit{branch} \& \textit{price} algorithm for the minimum cost clique cover problem in max-point tolerance graphs ⋮ On characterizing proper max-point-tolerance graphs ⋮ The partial order competition dimensions of bipartite graphs ⋮ An intersection model for multitolerance graphs: efficient algorithms and hierarchy ⋮ On central max-point-tolerance graphs ⋮ New Geometric Representations and Domination Problems on Tolerance and Multitolerance Graphs ⋮ Homothetic triangle representations of planar graphs ⋮ The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial

Uses Software

• Mathematica

This page was built for publication: Max-tolerance graphs as intersection graphs