On the complexity of recognizing Stick, BipHook and Max Point-Tolerance graphs

Stick graphs are defined as follows. Let A (respectively B) be a set of vertical (respectively horizontal) segments in the plane such that the bottom endpoints of the segments in A and the left endpoints of the segments in B lie on the same ground line with slope −1. The Stick graph defined by A and...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2023-03, Vol.952, p.113773, Article 113773
Main Author: Rusu, Irena
Format: Article
Language:English
Subjects:
BipHook graph
Intersection graph
Max point-tolerance graph
NP-hardness
Stick graph
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Stick graphs are defined as follows. Let A (respectively B) be a set of vertical (respectively horizontal) segments in the plane such that the bottom endpoints of the segments in A and the left endpoints of the segments in B lie on the same ground line with slope −1. The Stick graph defined by A and B, which is necessarily bipartite, is the intersection graph of the segments in A with the segments in B. We answer an open problem by showing that recognizing Stick graphs is NP-complete. This result allows us to easily solve two other open problems, namely the recognition of BipHook graphs and of max point-tolerance graphs. We show that both of them are NP-complete problems.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2023.113773