Intersection graph | EPFL Graph Search

In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types of sets that are used to form an intersection representation of them. Formal definition Formally, an intersection graph G is an undirected graph formed from a family of sets : S_i, ,,, i = 0, 1, 2, \dots by creating one vertex v{{sub|i}} for each set S{{sub|i}}, and connecting two vertices v{{sub|i}} and v{{sub|j}} by an edge whenever the corresponding two sets have a nonempty intersection, that is, : E(G) = { { v_i, v_j } \mid i \neq j, S_i \cap S_j \neq \empty }. All graphs are intersection graphs Any undirected graph G may be represented as an intersection graph. For each vertex vi of

Characterizing Path Graphs by Forbidden Induced Subgraphs

A path graph is the intersection graph of subpaths of a tree. In 1970, Renz asked for a characterization of path graphs by forbidden induced subgraphs. We answer this question by determining the complete list of graphs that are not path graphs and are minimal with this property. (C) 2009 Wiley Periodicals, Inc. J Graph Theory 62: 369-384, 2009

2009

Simple topological graphs

Andres Jacinto Ruiz Vargas

This thesis is devoted to the understanding of topological graphs. We consider the following four problems: 1. A \emph{simple topological graph} is a graph drawn in the plane so that its edges are represented by continuous arcs with the property that any two of them meet at most once, at endpoint or at a crossing. Let

G

be a complete simple topological graph on

n

vertices. The three edges induced by any triplet of vertices in

G

form a simple closed curve. If this curve contains no vertex in its interior (exterior), then we say that the triplet forms an \emph{empty triangle}. In 1998, Harborth proved that

G

has at least 2 empty triangles, and he conjectured that the number of empty triangles is at least

2n/3

. We settle Harborth's conjecture in the affirmative. 2. A \emph{monotone cylindrical} graph is a topological graph drawn on an open cylinder with an infinite vertical axis satisfying the condition that every vertical line intersects every edge at most once. It is called \emph{simple} if any pair of its edges have at most one point in common: an endpoint or a point at which they properly cross. We say that two edges are \emph{disjoint} if they do not intersect. We show that every simple complete monotone cylindrical graph on

n

vertices contains

\Omega(n^{1-\epsilon})

pairwise disjoint edges for any

\epsilon>0

. As a consequence, we show that every simple complete topological graph (drawn in the plane) with

n

vertices contains

\Omega(n^{\frac 12-\epsilon})

pairwise disjoint edges for any

\epsilon>0

. By extending some of the ideas here we are then able to get rid of the

\epsilon

term in the exponent, showing that in fact we can always guarantee a set with

\Omega(n^{\frac 12})

pairwise disjoint edges. This improves the previous lower bound of

\Omega(n^\frac 13)

by Suk and independently by Fulek. We remark that our proof implies a polynomial time algorithm for finding this set of pairwise disjoint edges. 3. A {\em tangle} is a graph drawn in the plane such that its edges are represented by continuous arcs, and any two edges share precisely one point, which is either a common endpoint or an interior point at which the two edges are tangent to each other. These points of tangencies are assumed to be distinct. If we drop the last assumption, that is, more than two edges may touch one another at the same point, then the drawing is called a {\em degenerate tangle}. We settle a problem of Pach, Radoi\v ci'c, and T'oth \cite{TTpaper}, by showing that every degenerate tangle has at most as many edges as vertices. We also give a complete characterization of tangles. 4. We show that for a constant

t\in \NN

, every simple topological graph on

n

vertices has

O(n)

edges if the graph has no two sets of

t

edges each such that every edge in one set is disjoint from all edges of the other set (i.e., the complement of the intersection graph of the edges is

K_{t,t}

-free). As an application, we settle the \emph{tangled-thrackle} conjecture formulated by Pach, Radoi\v{c}i'c, and T'oth: Every

n

-vertex graph drawn in the plane such that every pair of edges have precisely one point in common, where this point is either a common endpoint, a crossing, or a point of tangency, has at most

O(n)

edges.

EPFL2016

Triangle-Free Geometric Intersection Graphs with Large Chromatic Number

Michal Lason, Bartosz Maria Walczak

Several classical constructions illustrate the fact that the chromatic number of a graph may be arbitrarily large compared to its clique number. However, until very recently no such construction was known for intersection graphs of geometric objects in the plane. We provide a general construction that for any arc-connected compact set in that is not an axis-aligned rectangle and for any positive integer produces a family of sets, each obtained by an independent horizontal and vertical scaling and translation of , such that no three sets in pairwise intersect and . This provides a negative answer to a question of Gyarfas and Lehel for L-shapes. With extra conditions we also show how to construct a triangle-free family of homothetic (uniformly scaled) copies of a set with arbitrarily large chromatic number. This applies to many common shapes, like circles, square boundaries or equilateral L-shapes. Additionally, we reveal a surprising connection between coloring geometric objects in the plane and on-line coloring of intervals on the line.

Springer US2013

Simple topological graphs

Andres Jacinto Ruiz Vargas

G

be a complete simple topological graph on

n

vertices. The three edges induced by any triplet of vertices in

G

form a simple closed curve. If this curve contains no vertex in its interior (exterior), then we say that the triplet forms an \emph{empty triangle}. In 1998, Harborth proved that

G

has at least 2 empty triangles, and he conjectured that the number of empty triangles is at least

2n/3

n

vertices contains

\Omega(n^{1-\epsilon})

pairwise disjoint edges for any

\epsilon>0

. As a consequence, we show that every simple complete topological graph (drawn in the plane) with

n

vertices contains

\Omega(n^{\frac 12-\epsilon})

pairwise disjoint edges for any

\epsilon>0

. By extending some of the ideas here we are then able to get rid of the

\epsilon

term in the exponent, showing that in fact we can always guarantee a set with

\Omega(n^{\frac 12})

pairwise disjoint edges. This improves the previous lower bound of

\Omega(n^\frac 13)

t\in \NN

, every simple topological graph on

n

vertices has

O(n)

edges if the graph has no two sets of

t

edges each such that every edge in one set is disjoint from all edges of the other set (i.e., the complement of the intersection graph of the edges is

K_{t,t}

-free). As an application, we settle the \emph{tangled-thrackle} conjecture formulated by Pach, Radoi\v{c}i'c, and T'oth: Every

n

-vertex graph drawn in the plane such that every pair of edges have precisely one point in common, where this point is either a common endpoint, a crossing, or a point of tangency, has at most

O(n)

edges.

EPFL2016