On Local Structures of Cubicity 2 Graphs

DOI10.1007/978-3-319-48749-6_19zbMath1486.05204arXiv1603.09570OpenAlexW2964014571MaRDI QIDQ2958318

Sagnik Sen, Sujoy Bhore, Dibyayan Chakraborty, Sandip Das

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

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

Related Items (1)

On rectangle intersection graphs with stab number at most two

Cites Work

• Unnamed Item
• Recognizing graphs with fixed interval number is NP-complete
• Characterizing intersection classes of graphs
• The complexity of minimizing wire lengths in VLSI layouts
• Unit disk graphs
• A special planar satisfiability problem and a consequence of its NP- completeness
• Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity
• 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
• On a Special Class of Boxicity 2 Graphs

This page was built for publication: On Local Structures of Cubicity 2 Graphs