Narrow Results

In this paper we show that the treewidth of a circle graph can be computed in polynomial time. A circle graph is a graph that is isomorphic to the intersection graph of a finite collection of chords of a circle. The TREEWIDTH problem can be viewed upon as the problem of finding a chordal embedding of the graph that minimizes the clique number. Our algorithm to determine the treewidth of a circle graph can be implemented to run in O(n³) time, where n is the number of vertices of the graph.

Two recent publications describe realizable Gauss diagrams using conditions stating that the number of chords in certain sets of chords is even or odd. We demonstrate that these descriptions are incorrect by finding multiple counter-examples. However, the idea of having a parity-based description of realizable Gauss diagrams is attractive. We recall that realizability of Gauss diagrams as touch curves can be described via bipartite graphs. We show that realizable Gauss diagrams can be described via bipartite graphs.

A set D ⊆ V is a restrained dominating set of a graph G = (V, E) if every vertex in V\D is adjacent to a vertex in D and a vertex in V\D. Given a graph G and a positive integer k, the restrained domination problem is to check whether G has a restrained dominating set of size at most k. The restrained domination problem is known to be NP-complete even for chordal graphs. In this paper, we propose a linear time algorithm to compute a minimum restrained dominating set of a proper interval graph. We present a polynomial time reduction that proves the NP-completeness of the restrained domination problem for undirected path graphs, chordal bipartite graphs, circle graphs, and planar graphs.