2018/11/09 by Jan Bok, Bok, Jan, Nikola Jedličková +1
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #VLSI and FPGA Design Techniques
paper · pdf · doi:10.48550/arxiv.1811.04062
openalex publication_date 2018/11/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this short note, we show two NP-completeness results regarding the 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.