Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs

DOI10.1016/J.DAM.2023.06.013MaRDI QIDQ6064836zbMATH OpenOpenAlexFDO

Authors Flavia Bonomo, Gastón Abel Brito

Publication date 11 December 2023

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

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

zbMATH Keywords

forbidden patternsbipartite permutation graphsthinnessinterval bigraphsVPG graphsintersection graphs of rectangles

Mathematics Subject Classification ID

Distance in graphs (05C12) Structural characterization of families of graphs (05C75)

Abstract: The emph{thinness} of a graph is a width parameter that generalizes some properties of interval graphs, which are exactly the graphs of thinness one. Graphs with thinness at most two include, for example, bipartite convex graphs. Many NP-complete problems can be solved in polynomial time for graphs with bounded thinness, given a suitable representation of the graph. emph{Proper thinness} is defined analogously, generalizing proper interval graphs, and a larger family of NP-complete problems are known to be polynomially solvable for graphs with bounded proper thinness. The complexity of recognizing 2-thin and proper 2-thin graphs is still open. In this work, we present characterizations of 2-thin and proper 2-thin graphs as intersection graphs of rectangles in the plane, as vertex intersection graphs of paths on a grid (VPG graphs), and by forbidden ordered patterns. We also prove that independent 2-thin graphs are exactly the interval bigraphs, and that proper independent 2-thin graphs are exactly the bipartite permutation graphs. Finally, we take a step towards placing the thinness and its variations in the landscape of width parameters, by upper bounding the proper thinness in terms of the bandwidth.

Recommendations

• On the thinness and proper thinness of a graph
• Thinness and its variations on some graph families and coloring graphs of bounded thinness
• Thinness of product graphs
• Precedence thinness in graphs
• On the thinness of trees

Cites work

• scientific article; zbMATH DE number 3891425 (Why is no real title available?)
• scientific article; zbMATH DE number 4147519 (Why is no real title available?)
• scientific article; zbMATH DE number 15355 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• scientific article; zbMATH DE number 3307331 (Why is no real title available?)
• A linear-time algorithm for proper interval graph recognition
• A new property of critical imperfect graphs and some consequences
• Algorithms on circular-arc graphs
• An optimal greedy heuristic to color interval graphs
• Bipartite permutation graphs
• Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem
• Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs
• Comparability graphs and a new matroid
• Edge intersection graphs of single bend paths on a grid
• Edge intersection graphs of systems of paths on a grid with a bounded number of bends
• Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
• Graph classes and forbidden patterns on three vertices
• Graph minors. I. Excluding a forest
• Graph minors. III. Planar tree-width
• Interval bigraphs and circular arc graphs
• Max point-tolerance graphs
• On grounded -graphs and their relatives
• On the thinness and proper thinness of a graph
• Optimal labelling of a product of two paths
• Optimal packing and covering in the plane are NP-complete
• Ordering without forbidden patterns
• Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
• Recognizing interval bigraphs by forbidden patterns
• Recognizing interval digraphs and interval bigraphs in polynomial time
• Solving problems on generalized convex graphs via mim-width
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The bandwidth problem for graphs and matrices—a survey
• The stable set problem and the thinness of a graph
• Thinness of product graphs
• Topology of Thin Film RC Circuits
• Twin-width and transductions of proper k-mixed-thin graphs
• Twin-width. I: Tractable FO model checking
• Vertex Intersection Graphs of Paths on a Grid
• p-box: a new graph model

Cited in

(7)

• On the thinness of trees
• Exactly hittable interval graphs
• Forbidden pattern characterizations of 12-representable graphs defined by pattern-avoiding words
• Fair allocation algorithms for indivisible items under structured conflict constraints
• The simultaneous interval number: a new width parameter that measures the similarity to interval graphs
• Graph thinness: a lower bound and complexity
• Thinness and its variations on some graph families and coloring graphs of bounded thinness

This page was built for publication: Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs

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