Max point-tolerance graphs

DOI10.1016/J.DAM.2015.08.019zbMATH Open1350.05118arXiv1508.03810OpenAlexW2125939925MaRDI QIDQ344833FDOQ344833

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

Publication date: 24 November 2016

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

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.

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

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

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)

Cites Work

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

Cited In (25)

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

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)