Search

For every graph $H$, there exists a polynomial-time algorithm deciding if a planar input graph $G$ can be contracted to~$H$. However, the degree of the polynomial depends on the size of $H$. In this paper, we identify a class of graphs $\cal C$ such that for every $H \in \cal C$, there exists an algorithm deciding in time $f(|V(H)|) \cdot |V(G)|^{\bigO{1}}$ whether a planar graph $G$ can be contracted to~$H$. (The function $f(\cdot)$ does not depend on $G$.) The class $\cal C$ is the closure of planar triangulated graphs under taking of contractions. In fact, we prove that a graph $H \in \cal C$ if and only if there exists a constant $c_H$ such that if the tree-width of a graph is at least $c_H$, it contains $H$ as a contraction. We also provide a characterization of $\cal C$ in terms of minimal forbidden contractions., 11 pages, 3 figues

A proper circular-arc (PCA) model is a pair ${\cal M} = (C, \cal A)$ where $C$ is a circle and $\cal A$ is a family of inclusion-free arcs on $C$ in which no two arcs of $\cal A$ cover $C$. A PCA model $\cal U = (C,\cal A)$ is a $(c, \ell)$-CA model when $C$ has circumference $c$, all the arcs in $\cal A$ have length $\ell$, and all the extremes of the arcs in $\cal A$ are at a distance at least $1$. If $c \leq c'$ and $\ell \leq \ell'$ for every $(c', \ell')$-CA model equivalent (resp. isomorphic) to $\cal U$, then $\cal U$ is minimal (resp. minimum). In this article we prove that every PCA model is isomorphic to a minimum model. Our main tool is a new characterization of those PCA models that are equivalent to $(c,\ell)$-CA models, that allows us to conclude that $c$ and $\ell$ are integer when $\cal U$ is minimal. As a consequence, we obtain an $O(n^3)$ time and $O(n^2)$ space algorithm to solve the minimal representation problem, while we prove that the minimum representation problem is NP-complete., Comment: 22 pages, 18 figures

Although there are very algorithms for embedding graphs on unbounded grids, only few results on embedding or drawing graphs on restricted grids has been published. In this work, we consider the problem of embedding paths and cycles on grid graphs. We give the necessary and sufficient conditions for the existence of cycles of given length $k$ and paths of given length $k$ between two given vertices in $n$-vertex rectangular grid graphs and introduce two algorithms with running times O$(k)$ and O$(k^2)$ for finding respectively such cycles and paths. Also, we extend our results to $m\times n\times o$ 3D grids. Our method for finding cycle of length $k$ in rectangular grid graphs also introduces a linear-time algorithm for finding cycles of a given length $k$ in hamiltonian solid grid graphs.

Let $G$ be a finite undirected graph. A vertex {\em dominates} itself and all its neighbors in $G$. A vertex set $D$ is an {\em efficient dominating set} (\emph{e.d.}\ for short) of $G$ if every vertex of $G$ is dominated by exactly one vertex of $D$. The \emph{Efficient Domination} (ED) problem, which asks for the existence of an e.d.\ in $G$, is known to be \NP-complete even for very restricted graph classes such as for claw-free graphs, for chordal graphs and for $2P_3$-free graphs (and thus, for $P_7$-free graphs). We call a graph $F$ a {\em linear forest} if $F$ is cycle- and claw-free, i.e., its components are paths. Thus, the ED problem remains \NP-complete for $F$-free graphs, whenever $F$ is not a linear forest. Let WED denote the vertex-weighted version of the ED problem asking for an e.d. of minimum weight if one exists. In this paper, we show that WED is solvable in polynomial time for $(P_5+kP_2)$-free graphs for every fixed $k$, which solves an open problem, and, using modular decomposition, we improve known time bounds for WED on $(P_4+P_2)$-free graphs, $(P_6,S_{1,2,2})$-free graphs, and on $(2P_3,S_{1,2,2})$-free graphs and simplify proofs. For $F$-free graphs, the only remaining open case is WED on $P_6$-free graphs.