Max-tolerance graphs as intersection graphs

DOI10.1145/1109557.1109649MaRDI QIDQ3581555zbMATH OpenOpenAlexFDO

Authors 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)

Cited in

(13)

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

Describes a project that uses

Uses Software

• Mathematica

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

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