Max point-tolerance graphs

DOI10.1016/j.dam.2015.08.019zbMath1350.05118arXiv1508.03810OpenAlexW2125939925MaRDI QIDQ344833

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)

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

zbMATH Keywords

outerplanar graphstolerance graphscoloringinterval graphsweighted independent setclique coverL-graphsrectangle intersection graphs

Mathematics Subject Classification ID

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

Related Items (24)

Generalized disk graphs ⋮ On dominating set of some subclasses of string graphs ⋮ Coloring polygon visibility graphs and their generalizations ⋮ Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs ⋮ \(B_0\)-VPG representation of AT-free outerplanar graphs ⋮ 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 ⋮ On characterizing proper max-point-tolerance graphs ⋮ B0-VPG Representation of AT-free Outerplanar Graphs ⋮ On the complexity of recognizing Stick, BipHook and max point-tolerance graphs ⋮ Stick graphs with length constraints ⋮ Recognizing Stick Graphs with and without Length Constraints ⋮ Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames ⋮ Non-edge orientation and vertex ordering characterizations of some classes of bigraphs ⋮ Dominating set of rectangles intersecting a straight line ⋮ Recognition and drawing of stick graphs ⋮ Grid intersection graphs and order dimension ⋮ On central max-point-tolerance graphs ⋮ Terrain-like graphs: PTASs for guarding weakly-visible polygons and terrains ⋮ Covering and packing of triangles intersecting a straight line ⋮ On rectangle intersection graphs with stab number at most two ⋮ On grounded \(\llcorner\)-graphs and their relatives ⋮ Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames ⋮ Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve
• On orthogonal ray graphs
• On rigid circuit graphs
• A unified approach to domination problems on interval graphs
• A characterization of interval catch digraphs
• Linear algorithms to recognize outerplanar and maximal outerplanar 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
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• A recognition algorithm for the intersection graphs of paths in trees
• Algorithms for interval catch digraphs
• Coloring relatives of intervals on the plane. I: Chromatic number versus girth
• Linear-time recognition of circular-arc graphs
• Algorithmic graph theory and perfect graphs
• Characterization of the graphs with boxicity \(\leq 2\)
• Incidence matrices and interval graphs
• Approximating the minimum clique cover and other hard problems in subtree filament graphs
• Equilateral L-Contact Graphs
• Clique partitioning of interval graphs with submodular costs on the cliques
• Coloring and Maximum Independent Set of Rectangles
• Domination on Cocomparability Graphs
• Vertex Intersection Graphs of Paths on a Grid
• Representation of a finite graph by a set of intervals on the real line
• 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
• Max-tolerance graphs as intersection graphs
• Efficient Vertex- and Edge-Coloring of Outerplanar Graphs
• The Complexity of Coloring Circular Arcs and Chords
• On Triangle Contact Graphs
• Planar Graphs as VPG-Graphs
• Independent and Hitting Sets of Rectangles Intersecting a Diagonal Line
• Combinatorial and Geometric Properties of Planar Laman Graphs

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