Recognizing geometric intersection graphs stabbed by a line

DOI10.1016/j.tcs.2024.114488arXiv2209.01851OpenAlexW4392520387MaRDI QIDQ6204544

Irena Rusu, Kshitij Gajjar, Dibyayan Chakraborty

Publication date: 28 March 2024

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

complexityintersection graphNP-completenessgrounded L-graphstabbable grid intersection graph

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Fast partitioning \(l\)-apex graphs with applications to approximating maximum induced-subgraph problems
• Grid intersection graphs and order dimension
• Covering and coloring problems for relatives of intervals
• The book thickness of a graph
• On grid intersection graphs
• Label placement by maximum independent set in rectangles
• A special planar satisfiability problem and a consequence of its NP- completeness
• On bounding the chromatic number of L-graphs
• On dominating set of some subclasses of string graphs
• Finding geometric representations of apex graphs is NP-hard
• On grounded \(\llcorner\)-graphs and their relatives
• On the complexity of recognizing Stick, BipHook and max point-tolerance graphs
• Rectangle and Square Representations of Planar Graphs
• Characterizations of Deque and Queue Graphs
• Vertex Intersection Graphs of Paths on a Grid
• On a Coloring Problem.
• Representation of a finite graph by a set of intervals on the real line
• Fast and accurate algorithms for protein side-chain packing
• Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
• Computing maximum independent set on outerstring graphs and their relatives

This page was built for publication: Recognizing geometric intersection graphs stabbed by a line