Pith. sign in

REVIEW 1 cited by

A note on simultaneous representation problem for interval and circular-arc graphs

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1811.04062 v2 pith:QXJ46YIJ submitted 2018-11-09 cs.DM math.CO

Jan Bok , Nikola Jedličková This is my paper · ORCID
classification cs.DMmath.CO
keywords graphsrepresentationintervalproblemsimultaneouscircular-arcclassnote
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
abstract

In this short note, we show two NP-completeness results regarding the \emph{simultaneous representation problem}, introduced by Lubiw and Jampani. The simultaneous representation problem for a given class of intersection graphs asks if some $k$ graphs can be represented so that every vertex is represented by the same interval in each representation. We prove that it is NP-complete to decide this for the class of interval and circular-arc graphs in the case when $k$ is a part of the input and graphs are not in a sunflower position.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Simultaneous Representation of Proper and Unit Interval Graphs

    cs.DS 2019-08 accept novelty 7.0 of 10

    Simultaneous proper interval graphs can be recognized in linear time and simultaneous unit interval graphs in O(|V||E|) time in the sunflower case, and both become NP-complete without the sunflower restriction.

Pith tools