Extending partial representations of circular-arc graphs
From MaRDI portal
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.
Cites work
- A Kuratowski-type theorem for planarity of partially embedded graphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- Algorithms on circular-arc graphs
- An Efficient Test for Circular-Arc Graphs
- Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs
- Characterizations and recognition of circular-arc graphs and subclasses: a survey
- Complexity Results for Multiprocessor Scheduling under Resource Constraints
- Contact representations of planar graphs: extending a partial representation is hard
- Cyclic ordering is NP-complete
- Extending partial representations of circle graphs
- Extending partial representations of function graphs and permutation graphs
- Extending partial representations of subclasses of chordal graphs
- Extending partial representations of trapezoid graphs
- Incidence matrices and interval graphs
- Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
- Linear-time recognition of Helly circular-arc models and graphs
- Linear-time recognition of circular-arc graphs
- Matrix characterizations of circular-arc graphs
- Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs
- Normal Helly circular-arc graphs and its subclasses
- ON EXTENDING A PARTIAL STRAIGHT-LINE DRAWING
- PC trees and circular-ones arrangements.
- Proper Helly Circular-Arc Graphs
- Simple algorithms for partial and simultaneous rectangular duals with given contact orientations
- Simultaneous PQ-ordering with applications to constrained embedding problems
- Structure theorems for some circular-arc graphs
- Testing Planarity of Partially Embedded Graphs
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- The Complexity of Coloring Circular Arcs and Chords
- The intersection graphs of subtrees in trees are exactly the chordal graphs
Cited in
(4)
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)
