Structured Graphs and Algorithms
Org:
Jing Huang and Gary MacGillivray (University of Victoria)
[
PDF]
 JORGEN BANGJENSEN, 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_vv \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 2cycles.
We give a number of examples of polynomial instances as well as some
NPcompleteness proofs.
 ROSS CHURCHLEY, University of Victoria
Partitioning graphs via edgecoloured 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 edgecoloured homomorphisms, giving an efficient solution in restricted classes including clawfree, chordal, and cocomparability 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 lowdegree 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 NPcompleteness 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.