Who do we work with?
Our Working Groups
Science Communication
Talks by our Members and Guests
The modular decomposition (MD) of an undirected graph G is a natural
construction to capture key features of G in terms of a rooted labeled tree
(T,t) whose vertices are labeled as "series" (1), "parallel" (0) or "prime".
If a graph G does not contain prime modules, then all structural information of G
can be directly derived from its MD tree (T,t). As a consequence, many hard
problems become polynomial-time solvable on graphs without prime modules, since
the MD tree serves as a guide for algorithms to find efficient exact solutions
(e.g.\ for optimal colorings, maximum clique, isomorphism test, ... ).
However, the class of graphs without prime modules (aka cographs) is rather
restricted. We introduce here the novel concept of explicit modular decomposition
that aims at replacing "prime" vertices in the MD tree by suitable substructures
to obtain 0/1-labeled networks (N,t). Understanding which graphs can be
explained by which type of network does not only provide novel graph classes but
is crucial to understand which hard problem can be solved on which graph class
efficiently. We will mainly focus on graphs that can be explained by networks
(N,t) whose bi-connected components are simple cycles. These graphs are called
GaTEx, can be recognized in linear-time and are characterized by a set of 25
forbidden induced subgraphs. In particular, GaTEx graphs are closely related to
many other well-known graph classes such as P4-sparse and P4-reducible graphs,
weakly-chordal graphs, perfect graphs with perfect order, comparability and
permutation graphs. As a consequence, one can prove that many hard problems
become linear-time solvable on GaTEx graphs as well.
construction to capture key features of G in terms of a rooted labeled tree
(T,t) whose vertices are labeled as "series" (1), "parallel" (0) or "prime".
If a graph G does not contain prime modules, then all structural information of G
can be directly derived from its MD tree (T,t). As a consequence, many hard
problems become polynomial-time solvable on graphs without prime modules, since
the MD tree serves as a guide for algorithms to find efficient exact solutions
(e.g.\ for optimal colorings, maximum clique, isomorphism test, ... ).
However, the class of graphs without prime modules (aka cographs) is rather
restricted. We introduce here the novel concept of explicit modular decomposition
that aims at replacing "prime" vertices in the MD tree by suitable substructures
to obtain 0/1-labeled networks (N,t). Understanding which graphs can be
explained by which type of network does not only provide novel graph classes but
is crucial to understand which hard problem can be solved on which graph class
efficiently. We will mainly focus on graphs that can be explained by networks
(N,t) whose bi-connected components are simple cycles. These graphs are called
GaTEx, can be recognized in linear-time and are characterized by a set of 25
forbidden induced subgraphs. In particular, GaTEx graphs are closely related to
many other well-known graph classes such as P4-sparse and P4-reducible graphs,
weakly-chordal graphs, perfect graphs with perfect order, comparability and
permutation graphs. As a consequence, one can prove that many hard problems
become linear-time solvable on GaTEx graphs as well.
*What?*
TikZ (acronym for "TikZ ist kein Zeichenprogramm")is a tool to create
graphic elements in LaTeX. Not only graphs, but all kind of figures you
might think of.
*When/Where?*
Session 1: Tuesday November 21st, 11am to 1pm, in room 109.
There might be a zoom link to attend remotely, if interest in such an
arrangement is shown. Recording of the sessions will also be considered.
*For who?*
Any LaTeX user (not only graph enthusiasts) interested in creating nice
figures for their papers, posters, presentations...
The first session will introduce the basics. No previous knowledge of TikZ
is required.
TikZ (acronym for "TikZ ist kein Zeichenprogramm")is a tool to create
graphic elements in LaTeX. Not only graphs, but all kind of figures you
might think of.
*When/Where?*
Session 1: Tuesday November 21st, 11am to 1pm, in room 109.
There might be a zoom link to attend remotely, if interest in such an
arrangement is shown. Recording of the sessions will also be considered.
*For who?*
Any LaTeX user (not only graph enthusiasts) interested in creating nice
figures for their papers, posters, presentations...
The first session will introduce the basics. No previous knowledge of TikZ
is required.
*What?*
TikZ (acronym for "TikZ ist kein Zeichenprogramm")is a tool to create
graphic elements in LaTeX. Not only graphs, but all kind of figures you
might think of.
*When/Where?*
Session 2: Tuesday November 28th, 11am to 1pm, in room 109.
There might be a zoom link to attend remotely, if interest in such an
arrangement is shown. Recording of the sessions will also be considered.
*For who?*
Any LaTeX user (not only graph enthusiasts) interested in creating nice
figures for their papers, posters, presentations...
The second session will present some advanced techniques to draw more
complex figures. Experience with TikZ, or attendance of the first session,
is expected.
TikZ (acronym for "TikZ ist kein Zeichenprogramm")is a tool to create
graphic elements in LaTeX. Not only graphs, but all kind of figures you
might think of.
*When/Where?*
Session 2: Tuesday November 28th, 11am to 1pm, in room 109.
There might be a zoom link to attend remotely, if interest in such an
arrangement is shown. Recording of the sessions will also be considered.
*For who?*
Any LaTeX user (not only graph enthusiasts) interested in creating nice
figures for their papers, posters, presentations...
The second session will present some advanced techniques to draw more
complex figures. Experience with TikZ, or attendance of the first session,
is expected.