Max point-tolerance graphs

DOI10.1016/J.DAM.2015.08.019MaRDI QIDQ344833zbMATH OpenOpenAlexFDO

Authors Daniele Catanzaro, Steven Chaplick, Stefan Felsner, Bjarni V. Halldórsson, Magnús M. Halldórsson, Thomas Hixon, Juraj Stacho

Publication date 24 November 2016

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

Full work available at URL https://arxiv.org/abs/1508.03810

zbMATH Keywords

interval graphscoloringouterplanar graphsweighted independent setclique coverL-graphsrectangle intersection graphstolerance graphs

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Signed and weighted graphs (05C22)

Abstract: A graph $G$ is a emph{max point-tolerance (MPT)} graph if each vertex $v$ of $G$ can be mapped to a emph{pointed-interval} $(I_v,p_v)$ where $I_v$ is an interval of $mathbbR$ and $p_{v}in{I}_v$ such that $uv$ is an edge of $G$ iff $I_{u}cap{I}_{v}supseteq{p}_u,p_v$. MPT graphs model relationships among DNA fragments in genome-wide association studies as well as basic transmission problems in telecommunications. We formally introduce this graph class, characterize it, study combinatorial optimization problems on it, and relate it to several well known graph classes. We characterize MPT graphs as a special case of several 2D geometric intersection graphs; namely, triangle, rectangle, L-shape, and line segment intersection graphs. We further characterize MPT as having certain linear orders on their vertex set. Our last characterization is that MPT graphs are precisely obtained by intersecting special pairs of interval graphs. We also show that, on MPT graphs, the maximum weight independent set problem can be solved in polynomial time, the coloring problem is NP-complete, and the clique cover problem has a 2-approximation. Finally, we demonstrate several connections to known graph classes; e.g., MPT graphs strictly contain interval graphs and outerplanar graphs, but are incomparable to permutation, chordal, and planar graphs.

Recommendations

• On central max-point-tolerance graphs
• A \textit{branch} \& \textit{price} algorithm for the minimum cost clique cover problem in max-point tolerance graphs
• An intersection model for multitolerance graphs: efficient algorithms and hierarchy
• An intersection model for multitolerance graphs: efficient algorithms and hierarchy
• New geometric representations and domination problems on tolerance and multitolerance graphs

Cites work

• scientific article; zbMATH DE number 3853140 (Why is no real title available?)
• scientific article; zbMATH DE number 3877239 (Why is no real title available?)
• scientific article; zbMATH DE number 4200260 (Why is no real title available?)
• scientific article; zbMATH DE number 4045800 (Why is no real title available?)
• scientific article; zbMATH DE number 4063148 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2109336 (Why is no real title available?)
• scientific article; zbMATH DE number 2117210 (Why is no real title available?)
• A characterization of interval catch digraphs
• A digraph represented by a family of boxes or spheres
• A recognition algorithm for the intersection graphs of paths in trees
• A unified approach to domination problems on interval graphs
• A weighted min-max relation for intervals
• Algorithmic graph theory and perfect graphs
• Algorithms for interval catch digraphs
• Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve
• Approximating the minimum clique cover and other hard problems in subtree filament graphs
• Characterization of the graphs with boxicity \(\leq 2\)
• Clique partitioning of interval graphs with submodular costs on the cliques
• Coloring and maximum independent set of rectangles
• Coloring relatives of intervals on the plane. I: Chromatic number versus girth
• Combinatorial and geometric properties of planar Laman graphs
• Domination on Cocomparability Graphs
• Efficient Vertex- and Edge-Coloring of Outerplanar Graphs
• Equilateral L-contact graphs
• Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
• Incidence matrices and interval graphs
• Independent and hitting sets of rectangles intersecting a diagonal line
• Intersection graphs of curves in the plane
• Linear algorithms to recognize outerplanar and maximal outerplanar graphs
• Linear time algorithms on circular-arc graphs
• Linear-time recognition of circular-arc graphs
• Max-tolerance graphs as intersection graphs
• On Triangle Contact Graphs
• On orthogonal ray graphs
• On rigid circuit graphs
• Optimal packing and covering in the plane are NP-complete
• Planar graphs as VPG-graphs
• Representation of a finite graph by a set of intervals on the real line
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The Complexity of Coloring Circular Arcs and Chords
• Vertex Intersection Graphs of Paths on a Grid

Cited in

(24)

• Coloring polygon visibility graphs and their generalizations
• On characterizing proper max-point-tolerance graphs
• Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity
• On dominating set of some subclasses of string graphs
• Forbidden pattern characterizations of 12-representable graphs defined by pattern-avoiding words
• Generalized disk graphs
• Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames
• B0-VPG Representation of AT-free Outerplanar Graphs
• Approximating dominating set on intersection graphs of rectangles and L-frames
• A \textit{branch} \& \textit{price} algorithm for the minimum cost clique cover problem in max-point tolerance graphs
• Grounded \(\mathrm{L}\)-graphs are polynomially \(\chi \)-bounded
• \(B_0\)-VPG representation of AT-free outerplanar graphs
• Dominating set of rectangles intersecting a straight line
• On rectangle intersection graphs with stab number at most two
• On central max-point-tolerance graphs
• Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs
• Recognizing stick graphs with and without length constraints
• Grid intersection graphs and order dimension
• Stick graphs with length constraints
• On grounded \(\llcorner\)-graphs and their relatives
• Non-edge orientation and vertex ordering characterizations of some classes of bigraphs
• On the complexity of recognizing Stick, BipHook and max point-tolerance graphs
• Covering and packing of triangles intersecting a straight line
• Terrain-like graphs: PTASs for guarding weakly-visible polygons and terrains

This page was built for publication: Max point-tolerance graphs

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