-
Chapter and Conference Paper
Circle Graph Isomorphism in Almost Linear Time
Circle graphs are intersection graphs of chords of a circle. In this paper, we present a new algorithm for the circle graph isomorphism problem running in time ...
-
Chapter and Conference Paper
Graph Isomorphism Restricted by Lists
The complexity of graph isomorphism (GraphIso) is a famous problem in computer science. For graphs G and H, it asks whether they are the same up to a relabeling of vertices. In 1981, Lubiw proved that list restri...
-
Article
On the Classes of Interval Graphs of Limited Nesting and Count of Lengths
In 1969, Roberts introduced proper and unit interval graphs and proved that these classes are equal. Natural generalizations of unit interval graphs called k-length interval graphs were considered in which the nu...
-
Article
Extending Partial Representations of Interval Graphs
Interval graphs are intersection graphs of closed intervals of the real-line. The well-known computational problem, called recognition, asks whether an input graph G can be represented by closed intervals, i.e., ...
-
Article
Extending Partial Representations of Proper and Unit Interval Graphs
The recently introduced problem of extending partial interval representations asks, for an interval graph with some intervals pre-drawn by the input, whether the partial representation can be extended to a rep...
-
Chapter and Conference Paper
Cops and Robbers on String Graphs
The game of cops and robber, introduced by Nowakowski and Winkler in 1983, is played by two players on a graph. One controls k cops and the other a robber. The players alternate and move their pieces to the dista...
-
Chapter and Conference Paper
Minimal Obstructions for Partial Representations of Interval Graphs
Interval graphs are intersection graphs of closed intervals. A generalization of recognition called partial representation extension was introduced recently. The input gives an interval graph w...
-
Chapter and Conference Paper
Extending Partial Representations of Proper and Unit Interval Graphs
The recently introduced problem of extending partial interval representations asks, for an interval graph with some intervals pre-drawn by the input, whether the partial representation can be extended to a rep...
-
Chapter and Conference Paper
Algorithmic Aspects of Regular Graph Covers with Applications to Planar Graphs
A graph G covers a graph H if there exists a locally bijective homomorphism from G to H. We deal with regular covers in which this locally bijective homomorphism is prescribed by an action of a su...
-
Chapter and Conference Paper
Bounded Representations of Interval and Proper Interval Graphs
Klavík et al. [ar**v:1207.6960] recently introduced a generalization of recognition called the bounded representation problem which we study for the classes of interval and proper interval graphs. The input gives...
-
Chapter and Conference Paper
Cops and Robbers on Intersection Graphs
The game of cops and robber, introduced by Nowakowski and Winkler in 1983, is played by two players on a graph G, one controlling k cops and the other one robber, all positioned on V ...
-
Chapter and Conference Paper
Extending Partial Representations of Circle Graphs
The partial representation extension problem is a recently introduced generalization of the recognition problem. A circle graph is an intersection graph of chords of a circle. We study th...
-
Chapter and Conference Paper
Extending Partial Representations of Function Graphs and Permutation Graphs
Function graphs are graphs representable by intersections of continuous real-valued functions on the interval [0,1] and are known to be exactly the complements of comparability graphs. As such they are recogni...
-
Chapter and Conference Paper
MSOL Restricted Contractibility to Planar Graphs
We study the computational complexity of graph planarization via edge contraction. The problem Contract asks whether there exists a set S of at most k edges that when contracted produces a planar graph. We give a...
-
Chapter and Conference Paper
Extending Partial Representations of Subclasses of Chordal Graphs
Chordal graphs are intersection graphs of subtrees in a tree. We investigate complexity of the partial representation extension problem for chordal graphs. A partial representation specifies a tree T′ and some pr...
-
Chapter and Conference Paper
On the Complexity of Planar Covering of Small Graphs
The problem Cover(H) asks whether an input graph G covers a fixed graph H (i.e., whether there exists a homomorphism G → H which locally preserves the structure of the graphs). Complexity of this problem has been...
-
Chapter and Conference Paper
Extending Partial Representations of Interval Graphs
We initiate the study of the computational complexity of the question of extending partial representations of geometric intersection graphs. In this paper we consider classes of interval graphs – given a colle...
-
Chapter and Conference Paper
Structural and Complexity Aspects of Line Systems of Graphs
We study line systems in metric spaces induced by graphs. A line is a subset of vertices defined by a relation of betweenness.
