On local structures of cubicity 2 graphs

DOI10.1007/978-3-319-48749-6_19MaRDI QIDQ2958318zbMATH OpenOpenAlexFDO

Authors Sujoy Bhore, Dibyayan Chakraborty, Sandip Das, Sagnik Sen

Publication date 1 February 2017

Published in Combinatorial Optimization and Applications (Search for Journal in Brave)

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

zbMATH Keywords

2-stab unit interval graph2SUIG representation

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: A 2-stab unit interval graph (2SUIG) is an axes-parallel unit square intersection graph where the unit squares intersect either of the two fixed lines parallel to the $X$-axis, distance $1+epsilon$ ($0<epsilon<1$) apart. This family of graphs allow us to study local structures of unit square intersection graphs, that is, graphs with cubicity 2. The complexity of determining whether a tree has cubicity 2 is unknown while the graph recognition problem for unit square intersection graph is known to be NP-hard. We present a polynomial time algorithm for recognizing trees that admit a 2SUIG representation.

Recommendations

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

Cites work

• A special planar satisfiability problem and a consequence of its NP- completeness
• Characterizing intersection classes of graphs
• Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
• scientific article; zbMATH DE number 3307331 (Why is no real title available?)
• Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity
• On a special class of boxicity 2 graphs
• Recognizing graphs with fixed interval number is NP-complete
• Representation of a finite graph by a set of intervals on the real line
• The complexity of minimizing wire lengths in VLSI layouts
• Unit disk graphs

Cited in

(6)

• Graphs which locally mirror the hypercube structure
• Structure of the \(Fi_{24}^\prime\) maximal 2-local geometry point-line collinearity graph
• scientific article; zbMATH DE number 6890355 (Why is no real title available?)
• On a special class of boxicity 2 graphs
• On rectangle intersection graphs with stab number at most two
• On the stab number of rectangle intersection graphs

This page was built for publication: On local structures of cubicity 2 graphs

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