CanaDAM 2011
Université de Victoria, 31 mai - 3 juin 2011

Structured Graphs and Algorithms
Org: Jing Huang and Gary MacGillivray (University of Victoria)

JORGEN BANG-JENSEN, University of Southern Denmark
Finding an induced subdivision of a digraph  [PDF]

We consider the following problem for oriented graphs and digraphs: Given an oriented graph (digraph) $H$; does it contain an induced subdivision of a prescribed oriented graph (digraph) $D$? That is, can we find $|V(D)|$ distinct vertices $\{h_v|v \in V(D)\}$ in $H$ such that for every arc $uv$ of $D$ there is an induced path $P_{uv}$ from $h_u$ to $h_v$ in H and furthermore there is no arc in $H$ between distinct paths $P_{uv},P_{u^\prime v^\prime}$ (i.e., no arc with precisely one end on $P_{uv}$ and the other on $P_{u^\prime v^\prime}$ )? The complexity of this problem depends on whether $H$ is an oriented graph or contains 2-cycles. We give a number of examples of polynomial instances as well as some NP-completeness proofs.

ROSS CHURCHLEY, University of Victoria
Partitioning graphs via edge-coloured homomorphisms  [PDF]

Graph homomorphisms give structure to a large class of graph partition problems. However, many problems do not obviously have a homomorphism model. The {\em monopolar partition problem}, for example, asks whether the vertices of a graph can be partitioned into an independent set and an induced $P_3$-free subgraph. We relate monopolar partitions to certain edge-coloured homomorphisms, giving an efficient solution in restricted classes including claw-free, chordal, and co-comparability graphs.

MATHEW FRANCIS, University of Toronto
Intersection dimensions of graphs  [PDF]

By $G=G_1\cap G_2$, we mean that $V(G)=V(G_1)=V(G_2)$ and $E(G)=E(G_1)\cap E(G_2)$. The intersection dimension of a graph $G$ with respect to a graph class $\mathcal{A}$ is $\mathrm{dim}_\mathcal{A}(G)=\min~\{k~|~\exists G_1,\ldots,G_k\in\mathcal{A}\mbox{ and } G=G_1\cap\cdots\cap G_k\}$. Given two classes of graphs $\mathcal{A}$ and $\mathcal{B}$, the intersection dimension of $\mathcal{A}$ with respect to $\mathcal{B}$, $\mathrm{dim}_\mathcal{B}\mathcal{A}=\sup_{G\in \mathcal{A}}~\mathrm{dim}_\mathcal{B}(G)$. We explore the intersection dimensions of some classes of graphs like planar graphs, split graphs, permutation graphs and cocomparability graphs with respect to each other.

JING HUANG, University of Victoria
Chronological interval digraphs  [PDF]

Interval graphs admit elegant structural characterizations and linear time recognition algorithms; On the other hand, the usual interval digraphs lack a forbidden structural characterization as well as a low-degree polynomial time recognition algorithm. We identify a class of interval digraphs which we call chronological interval digraphs and argue that they are the most natural digraphs analogues of interval graphs. This work is joint with Das and Hell.

RAGNAR NEVRIES, University of Rostock
Recognizing polar and monopolar graphs  [PDF]

Polar graphs admit a vertex partition into a complete multipartite graph and a $P_3$-free graph. Special cases of polar graphs are monopolar graphs, in which the complete multipartite graph is a stable set and unipolar graphs, where it is a clique. While recognizing unipolar graphs is efficiently doable for every input graph, checking polarity or monopolarity is hard in general and known to be easy on only few graph classes.

We give new, sharp NP-completeness results; in particular we show that recognizing polar planar and monopolar planar graphs is hard. On the other hand we give positive results for polarity on subclasses of planar graphs. These results rely on a new technique for solving monopolarity on a large graph class.

Handling of online submissions has been provided by the CMS.


Centre de recherches mathématiques Fields Institute MITACS Pacific Institute for the Mathematical Sciences Société mathématique du Canada University of Victoria