On the stab number of rectangle intersection graphs

DOI10.1007/S00224-019-09936-WzbMATH Open1442.05187arXiv1804.06571OpenAlexW2973031495MaRDI QIDQ778517FDOQ778517

Authors: Dibyayan Chakraborty, Mathew C. Francis 

Publication date: 2 July 2020

Published in: Theory of Computing Systems (Search for Journal in Brave)

Abstract: We introduce the notion of emph{stab number} and emph{exact stab number} of rectangle intersection graphs, otherwise known as graphs of boxicity at most 2. A graph $G$ is said to be a emph{$k$-stabbable rectangle intersection graph}, or emph{$k$-SRIG} for short, if it has a rectangle intersection representation in which $k$ horizontal lines can be chosen such that each rectangle is intersected by at least one of them. If there exists such a representation with the additional property that each rectangle intersects exactly one of the $k$ horizontal lines, then the graph $G$ is said to be a emph{$k$-exactly stabbable rectangle intersection graph}, or emph{$k$-ESRIG} for short. The stab number of a graph $G$, denoted by $stab(G)$, is the minimum integer $k$ such that $G$ is a $k$-SRIG. Similarly, the exact stab number of a graph $G$, denoted by $estab(G)$, is the minimum integer $k$ such that $G$ is a $k$-ESRIG. In this work, we study the stab number and exact stab number of some subclasses of rectangle intersection graphs. A lower bound on the stab number of rectangle intersection graphs in terms of its pathwidth and clique number is shown. Tight upper bounds on the exact stab number of split graphs with boxicity at most 2 and block graphs are also given. We show that for $kleq3$, $k$-SRIG is equivalent to $k$-ESRIG and for any $kgeq10$, there is a tree which is a $k$-SRIG but not a $k$-ESRIG. We also develop a forbidden structure characterization for block graphs that are 2-ESRIG and trees that are 3-ESRIG, which lead to polynomial-time recognition algorithms for these two classes of graphs. These forbidden structures are natural generalizations of asteroidal triples. Finally, we construct examples to show that these forbidden structures are not sufficient to characterize block graphs that are 3-SRIG or trees that are $k$-SRIG for any $kgeq4$.

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

Recommendations

• On rectangle intersection graphs with stab number at most two
• On rectangle intersection graphs with stab number at most two
• On a special class of boxicity 2 graphs
• On local structures of cubicity 2 graphs

zbMATH Keywords

interval graphsblock graphsrectangle intersection graphsasteroidal triple\(k\)-SRIGforbidden structure characterizationstab number

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• Representation of a finite graph by a set of intervals on the real line
• The Complexity of the Partial Order Dimension Problem
• A special planar satisfiability problem and a consequence of its NP- completeness
• Boxicity and treewidth
• On a Coloring Problem.
• The hardness of approximating the boxicity, cubicity and threshold dimension of a graph
• Boxicity of graphs on surfaces
• The LBFS structure and recognition of interval graphs
• Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
• Title not available (Why is that?)
• Independent and hitting sets of rectangles intersecting a diagonal line
• PTAS for weighted set cover on unit squares
• Label placement by maximum independent set in rectangles
• Lower bounds on the pathwidth of some grid-like graphs
• Boxicity and maximum degree
• Computing the boxicity of a graph by covering its complement by cointerval graphs
• A note on maximum independent sets in rectangle intersection graphs
• PATHWIDTH AND LAYERED DRAWINGS OF TREES
• Lower bounds for boxicity
• On a special class of boxicity 2 graphs
• Upper bound on cubicity in terms of boxicity for graphs of low chromatic number

Cited In (6)

• On local structures of cubicity 2 graphs
• The maximum number of ways to stab n convex nonintersecting sets in the plane is 2n-2
• Exactly hittable interval graphs
• On rectangle intersection graphs with stab number at most two
• On rectangle intersection graphs with stab number at most two
• On a special class of boxicity 2 graphs

This page was built for publication: On the stab number of rectangle intersection graphs

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