Extending partial representations of circular-arc graphs
From MaRDI portal
Publication:6043187
DOI10.1007/978-3-031-15914-5_17arXiv2108.13076MaRDI QIDQ6043187FDOQ6043187
Authors: Jiří Fiala, Ignaz Rutter, Peter Stumpf, Peter Zeman 
Publication date: 5 May 2023
Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
Abstract: The partial representation extension problem generalizes the recognition problem for classes of graphs defined in terms of vertex representations. We exhibit circular-arc graphs as the first example of a graph class where the recognition is polynomially solvable while the representation extension problem is NP-complete. In this setting, several arcs are predrawn and we ask whether this partial representation can be completed. We complement this hardness argument with tractability results of the representation extension problem on various subclasses of circular-arc graphs, most notably on all variants of Helly circular-arc graphs. In particular, we give linear-time algorithms for extending normal proper Helly and proper Helly representations. For normal Helly circular-arc representations we give an -time algorithm. Surprisingly, for Helly representations, the complexity hinges on the seemingly irrelevant detail of whether the predrawn arcs have distinct or non-distinct endpoints: In the former case the previous algorithm can be extended, whereas the latter case turns out to be NP-complete. We also prove that representation extension problem of unit circular-arc graphs is NP-complete.
Full work available at URL: https://arxiv.org/abs/2108.13076
Cites Work
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Linear-time recognition of circular-arc graphs
- Incidence matrices and interval graphs
- The Complexity of Coloring Circular Arcs and Chords
- Algorithms on circular-arc graphs
- Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
- Linear-time recognition of Helly circular-arc models and graphs
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Complexity Results for Multiprocessor Scheduling under Resource Constraints
- Algorithmic Aspects of Vertex Elimination on Graphs
- A Kuratowski-type theorem for planarity of partially embedded graphs
- ON EXTENDING A PARTIAL STRAIGHT-LINE DRAWING
- Characterizations and recognition of circular-arc graphs and subclasses: a survey
- Normal Helly circular-arc graphs and its subclasses
- Structure theorems for some circular-arc graphs
- PC trees and circular-ones arrangements.
- Matrix characterizations of circular-arc graphs
- Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs
- Cyclic ordering is NP-complete
- Proper Helly Circular-Arc Graphs
- Testing Planarity of Partially Embedded Graphs
- Extending partial representations of subclasses of chordal graphs
- Extending partial representations of function graphs and permutation graphs
- Contact representations of planar graphs: extending a partial representation is hard
- Extending partial representations of circle graphs
- An Efficient Test for Circular-Arc Graphs
- Extending partial representations of trapezoid graphs
- Simultaneous PQ-ordering with applications to constrained embedding problems
- Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs
- Simple algorithms for partial and simultaneous rectangular duals with given contact orientations
Cited In (3)
This page was built for publication: Extending partial representations of circular-arc graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6043187)
