NDMI037 Geometric representations of graphs I - 2025/26

Monday 14:00 - S6

Sept 29, 2025
Introduction of the graphs classes we will see during the lecture
Chordal graphs
Definitions: chordal graphs, simplicial vertices, perfect elimination scheme (PES), clique-tree decomposition
Lemmas: every minimal vertex cut in a chordal graph induces a complete subgraph, every chordal graph is either complete or contains two non-adjacent simplicial vertices
Theorem: The following statements are equivalent for every graph G

• G is chordal
• G has a PES
• G has a clique-tree decomposition
• G is isomorphic to the intersection graph of a collection of subtrees of a tree.

Oct 6, 2025
Interval graphs, comparability graphs, permutation and function graphs
Interval graphs Interval graphs are intersection graphs of intervals on a line, equivalently intersection graphs of subtrees (i.e., subpaths) of paths. A graph is an interval graph iff it allowx a clique-path decomposition.
Comparability graphs are graphs of comparability relation in partially ordered sets.
Main characterization theorem.

• FUN = co-CO Function graphs are exactly complements of comparability graphs
• PER = CO ∩ co-CO Permutation graphs are graphs that are both comparability graphs and complements of those
• INT = CHOR ∩ co-CO Interval graphs are graphs that are both chordal and complements of comparability graphs.

Oct 13, 2025
Interval filament graphs
Interval filaments are curves lying in a halfplane above an interval, with endpoints in the endpoints of the interval. IFA graphs are intersection graphs of interval filaments (all in the same halfplane, with their underlying intervals on the boundary line).
For a graph class A , A-mixed graphs G=(V,E) are graphs that allow a partition E=E1 ∪ E2 and a transitive oriontation tr(E2) such that

• (V,E1) ∈ A
• for every three vertices u,v,w, uv ∈ tr(E2) and vw ∈ E1 implies uw ∈ E1.

Fanica Gavril: Maximum weight independent sets and cliques in intersection graphs of filaments. Inf. Process. Lett. 73(5-6): 181-188 (2000)
See also handout No. 3 from 2021 in SIS

Oct 20, 2025
INDEPENDENT SET and CLIQUE in intersection graphs
WEIGHTED CLIQUE is polynomial time solvable in interval graphs, because such graphs have only linearly many inclusion-wise maximal cliques.
WEIGHTED INDEPENDENT SET is polynomial time solvable in interval graphs by dynamic programming.
Main theorem: If WEIGHTED CLIQUE is polynomial time solvable in graphs from class A , then it is polynomial time solvable also in A-mixed graphs. The algorithm is again dynamic programming, but more sophisticated.
Corollary: WEIGHTED INDEPENDENT SET is polynomial time solvable in interval filament graphs.

Fanica Gavril: Maximum weight independent sets and cliques in intersection graphs of filaments. Inf. Process. Lett. 73(5-6): 181-188 (2000)
See also handout No. 4 from 2021 in SIS

Oct 27, 2025
Recognition of chordal graphs
Linear time algorithms LexBFS (for constructing a candidate for a PES) and (for testing if a linear ordering of vertices is a PES).

M. C. Golumbic: Algorithmic Graph Theory and Perfect Graphs, Elsevier, 2004
See also handout No. 5 from 2021 in SIS

Nov 3, 2025
Structure of transitive orientations of graphs
The block B(xy) of the orientation xy of an edge {x,y} ∈ E is the smallest relation B ⊂ VxV such that
(ab ∈ B) & ({a,c} ∈ E) & ({b,c} ∉ E) implies ac ∈ B
(and likewise (ba ∈ B) & ({a,c} ∈ E) & ({b,c} ∉ E) implies ca∈ B).
The main theorem says that G is transitively orientable if and only if B(xy) is antisymmetric for every edge {x,y} ∈ E.
A polynomial-time recognition algorithm of transitively orientable graphs follows from the main theorem.

M. C. Golumbic: Algorithmic Graph Theory and Perfect Graphs, Elsevier, 2004
See also handout No. 6 from 2021 in SIS

Nov 10, 2025
Boxicity of graphs.
Every bipartite graph of boxicity 2 is a grid intersection graph.

S. Bellantoni, Irith Ben-Arroyo Hartman, Teresa M. Przytycka, Sue Whitesides: Grid intersection graphs and boxicity. Discrete Mathematics 114(1-3): 41-49 (1993)
See also handout No. 8 from 2021 in SIS.

Nov 24, 2025
String graphs and Abstract topological graphs I
Every string graph has a representation with a finite number of crossing points. Outerstring and constrained outerstring graphs. Complements of cycles of length at least 4 are not constrained outerstring with respect to the natural cyclic order of vertices.
Abstract topological graphs, weak and strong realizability. Polynomial equivalence of strong realizability of AT-graphs with recognition of string graphs.
Sizes of representations. There are AT-graphs which require exponential number of crossing points in every (weak or strong) realization. Every weak realizable AT-graph has a weak realization with at most n2ⁿ crossing points.

F. W. Sinden: Topology of thin film RC circuits, Bell System Technical Journal 45 (9): 1639-1662 (1966)
Jan Kratochvíl, Jirí Matousek: String graphs requiring exponential representations. J. Comb. Theory, Ser. B 53(1): 1-4 (1991)
Marcus Schaefer, Daniel Stefankovic: Decidability of string graphs. J. Comput. Syst. Sci. 68(2): 319-334 (2004)

Dec 8, 2025
Grid contact representations of planar bipartite graphs
An s-t numbering of a graph is an acyclic orientation with exactly one source and exactly one sink. Theorem 1: Every plane vertex-2-connected graph has an s-t numbering and an upward planar drawing which respects this numbering.
Rectangle visibility representations of plane graphs - vertices are represented by horizontal segments, faces by vertical ones. Edges correspond to visibility relations within the rectangles formed by touching segments (crossings are not allowed). Theorem 2: Every plane vertex-2-connected graph has a rectangle visibility representation.
Grid contact representations. Observation: Every grid contact graph is planar and bipartite. Theorem 3: Every planar bipartite graph is a grid contact graph.

See also handout No. 7 from 2021 in SIS.