Given a set of red and blue points, an orthogeodesic alternating path is a path such that each edge is a geodesic orthogonal chain connecting points of different colour and no two edges cross. We consider the problem of deciding whether there exists a Hamiltonian orthogeodesic alternating path, i.e., an orthogeodesic alternating path visiting all points. We provide an O(n log ²n)-time algorithm for finding such a path if no two points are horizontally or vertically aligned. We show that the problem is NP-hard if bends must be at grid points. Nevertheless, we can approximate the maximum number of vertices of an orthogeodesic alternating path on the grid by roughly a factor of 3. Finally, we consider the problem of findinggorthogeodesic alternating matchings, cycles, and trees.

The rotator graph has vertices labeled by the permutations of n in one line notation, and there is an arc from u to v if a prefix of u's label can be rotated to obtain v's label. In other words, it is the directed Cayley graph whose generators are σ(k) := (1 2 ... k) for 2 ≤ k ≤ n and these rotations are applied to the indices of a permutation. In a restricted rotator graph the allowable rotations are restricted from k in {2,3,...,n} to k in G where G is some smaller (finite) subset of {2,3,...,n}. We construct Hamilton cycles for G = {n-1, n} and G = {2, 3, n}, and provide efficient iterative algorithms for generating them. Our results start with a Hamilton cycle in the rotator graph due to Corbett (IEEE Transactions on Parallel and Distributed Systems 3 (1992) 622-626) and are constructed entirely from two sequence operations we name `reusing' and `recycling'.

A 2-layer drawing represents a bipartite graph where each vertex is a point on one of two parallel lines, no two collinear vertices are adjacent, and the edges are straight-line segments. In this paper we study 2-layer drawings where all edge crossings form right angles.We characterize which graphs admit this type of drawing, provide linear-time testing and embedding algorithms, and present a polynomial-time crossing minimization technique. Also, for a given graph G and a constant k, we prove that it is NP-complete to decide whether G contains a subgraph of at least k edges having a 2-layer drawing with right angle crossings.

We study the minimum number of label transitions around a given vertex v₀ in a planar multigraph G in which the edges incident with v₀ are labelled with integers 1, ... ,r, where the minimum is taken over all embeddings of G in the plane. For a fixed number of labels, a polynomial-time algorithm that computes the minimum number of label transitions around v₀ is presented. The algorithm is fixed-parameter tractable. If the number of labels is arbitrary, then the problem of deciding whether the minimum number of label transitions is at most k is NP-complete.

We investigate the question of which graphs have planar emulators (a locally-surjective homomorphism from some finite planar graph)---a problem raised already in Fellows' thesis (1985) and conceptually related to the better known planar cover conjecture by Negami (1986). For over two decades, the planar emulator problem lived poorly in a shadow of Negami's conjecture---which is still open---as the two were considered equivalent. But, in the end of 2008, a surprising construction by Rieck and Yamashita falsified the natural "planar emulator conjecture", and thus opened a whole new research field. We present further results and constructions which show how far the planar-emulability concept is from planar-coverability, and that the traditional idea of likening it to projective embeddability is actually very out-of-place. We also present several positive partial characterizations of planar-emulable graphs.

An acyclic coloring of a graph G is a coloring of the vertices of G, where no two adjacent vertices of G receive the same color and no cycle of G is bichromatic. An acyclic k-coloring of G is an acyclic coloring of G using at most k colors. In this paper we prove that any triangulated plane graph G with n vertices has a subdivision that is acyclically 4-colorable where the number of division vertices is at most 2n-6. We also prove that every triconnected plane cubic graph has a subdivision that is acyclically 3-colorable where the number of division vertices is at most n/2. We show that it is NP-complete to decide whether a graph with degree at most 7 is acyclically 4-colorable or not. Furthermore, we give some sufficient conditions on the number of division vertices for acyclic coloring of subdivisions of partial k-trees.

In this paper we initiate a systematic study of a problem that has the flavor of two classical problems, namely COLORING and DOMINATION, from the perspective of algorithms and complexity. A dominator coloring of a graph G is an assignment of colors to the vertices of G such that it is a proper coloring and every vertex dominates all the vertices of at least one color class. The minimum number of colors required for a dominator coloring of G is called the dominator chromatic number of G and is denoted by χ_d(G). In the Dominator Coloring (DC) problem, a graph G and a positive integer k are given as input and the objective is to check whether χ_d(G) ≤ k. We first show that DC is NP-complete on certain restricted classes of graphs, namely bipartite graphs, planar graphs and split graphs. This answers an open problem posed by Chellali and Maffra [Dominator Colorings in Some Classes of Graphs, Graphs and Combinatorics, 2011] about the polynomial time solvability of DC on chordal graphs in the negative. We then complement these hardness results by showing that the problem is fixed parameter tractable (FPT) on chordal graphs and in graphs which exclude a fixed apex graph as a minor. We also show that the problem can be solved in linear time on trees, resolving another open problem due to Chellali and Maffra.

In this paper, we study a new colouring problem up to our best knowledge inspired by the imperative of practical networks. In real-life wireless networks, nodes interfere with one another with various intensities depending on numerous parameters: distance between them, the geographical topography, obstacles, etc. We model this with a noise matrix. The interference perceived by a node then is the sum of all the noise of the nodes emitting on the same frequency. The problem is then to determine the minimum number of colours (or frequencies) needed to colour the whole graph so that the interference does not exceed a given threshold. We provide several general results, such as bounds on this number of colours (e.g. a Brook's like theorem). We then study the practical case of square of infinite grids which corresponds to operators' network and a noise decreasing with the distance. We provide the chromatic number of the square, triangular and hexagonal grids for all possible admissible interference levels. Finally, we model the problem using linear programming, propose and test a heuristic and an exact branch & bound algorithms on random cell-like graphs, namely the Poisson Voronoi tessellations.

The Cluster Editing problem asks to transform a graph by at most k edge modifications into a disjoint union of cliques. The problem is NP-complete, but several parameterized algorithms are known. We present a novel search tree algorithm for the problem, which improves running time from O^*(1.76^k) to O^*(1.62^kk). In detail, we can show that we can always branch with branching vector (2,1) or better, resulting in the golden ratio as the base of the search tree size. Our algorithm uses a well-known transformation to the integer-weighted counterpart of the problem. To achieve our result, we combine three techniques: First, we show that zero-edges in the graph enforce structural features that allow us to branch more efficiently. Second, by repeatedly branching we can isolate vertices, releasing costs. Finally, we use a known characterization of graphs with few conflicts.

The guarding game is a game in which several cops have to guard a region in a (directed or undirected) graph against a robber. The robber and the cops are placed on vertices of the graph; they take turns in moving to adjacent vertices (or staying), cops inside the guarded region, the robber on the remaining vertices (the robber-region). The goal of the robber is to enter the guarded region at a vertex with no cop on it. The problem is to determine whether for a given graph and given number of cops the cops are able to prevent the robber from entering the guarded region. The problem is highly nontrivial even for very simple graphs. It is known that when the robber-region is a tree, the problem is NP-complete, and if the robber-region is a directed acyclic graph,the problem becomes PSPACE-complete [Fomin, Golovach, Hall, Mihalak, Vicari, Widmayer: How to Guard a Graph? Algorithmica, DOI: 10.1007/s00453-009-9382-4].We solve the question asked by Fomin et al. in the previously mentioned paper and we show that if the graph is arbitrary (directed or undirected),the problem becomes E-complete.

We study a constrained version of the knapsack problem in which dependencies between items are given by the adjacencies of a graph. In the 1-neighbour knapsack problem, an item can be selected only if at least one of its neighbours is also selected. We give approximation algorithms and hardness results when the nodes have both uniform and arbitrary weight and profit functions, and when the dependency graph is directed and undirected.

We provide a new characterization of the NP-hard arc routing problem Rural Postman in terms of a constrained variant of minimum-weight perfect matching on bipartite graphs. To this end, we employ a parameterized equivalence between Rural Postman and Eulerian Extension, a natural arc addition problem in directed multigraphs. We indicate the NP-hardness of the introduced matching problem. In particular, we use it to make some partial progress with respect to answering the open question about the parameterized complexity of Rural Postman with respect to the number of weakly connected components in the graph induced by the required arcs, this being a more than thirty years open and long-time neglected question with signiﬁcant practical relevance.

The stable transversal problem for a fixed graph H asks whether a graph contains a stable set that meets every induced copy of H in the graph. Stable transversal problems generalize several vertex partition problems and have been studied for various classes of graphs. Following a result of Farrugia, the stable transversal problem for each C_k with k ≥ 3 is NP-complete. In this paper, we study an ‘edge version’ of these problems. Specifically, we investigate the problem of determining whether a graph contains a matching that meets every copy of H. We show that the problem for C₃ is polynomial and for each C_k with k ≥ 4 is NP-complete. Our results imply that the stable transversal problem for each C_k with k ≥ 4 remains NP-complete when it is restricted to line graphs. We show by contrast that the stable transversal problem for C₃, when restricted to line graphs, is polynomial.

This paper presents the first kinetic data structure (KDS) for maintenance of the Euclidean minimum spanning tree (EMST) on a set of moving points in 2-dimensional space which has been open since 1997. For a set of n points moving in the plane we build a KDS of size O(n) in O(n log n) preprocessing time by which their EMST is maintained efficiently during the motion. This is done by applying the required changes to the combinatorial structure of the EMST which is changed in discrete timestamps. We assume that the motion of the points, i.e. x and y coordinates of the points, are defined by algebraic functions of constant maximum degree of time. In terms of the KDS performance parameters, our KDS is responsive, local, and compact. The presented KDS is based on monitoring changes of the Delaunay triangulation of the points as well as edge-length changes only for the edges of the current Delaunay triangulation.

We propose a new algorithm that solves the Steiner tree problem on graphs with vertex set V to optimality in O(B_tw+2² tw |V|) time, where tw is the graph's treewidth and the Bell number B_k is the number of partitions of a k-element set. This is a linear time algorithm for graphs with fixed treewidth and a polynomial algorithm for tw = O(log|V|/loglog|V|). While being faster than the previously known algorithms, our thereby used coloring scheme can be extended to give new, improved algorithms for the prize-collecting Steiner tree as well as the k-cardinality tree problems.

IWOCA 2011: Abstracts for Session B