|
Geometric Graphs and Representations
Geometric graphs and representations are intensively
studied both for their practical motivation and interesting theoretical
properties. In the recent years, several monographs have been published in
this area, and several of the main open problems have been solved. The
workshop will present an overview of these, as well as point out those
that remain open and require more effort to be solved. Several leading
experts accepted the invitation to join the workshop.
Petr Hlineny (Masaryk University, Brno): On difficulty and
complexity of graph crossing number
Classical crossing number of a graph G is the smallest possible number
of pairwise edge-crossings over all drawings of G in the plane.
This parameter has important practical applications, for instance,
in VLSI design or graph visualization. Still, it is a very very difficult
parameter to handle. We briefly review the problem and some of its weird
properties. We focus on the computational complexity issues
associated with the crossing number problems, outline basic known results
and open problems.
Michael Kaufmann (University Tuebingen): Max-tolerance as geometric
intersection graphs
Max-tolerance graphs provide a generalization of interval graphs. Vertices
of the graph are represented by intervals, and with each interval is
associated a number (called its tolerance). Two vertices are adjacent if
the overlap of their intervals is greater or equal than both their
tolerances. We will show how max-tolerance graphs arise naturally in a DNA
sequencing problem. We will further show that max-tolerance graphs are
exactly intersection graphs of congruent triangles in the plane, and
exploit this equivalent formulation to gain new insight into this class of
graphs. In particular, we will show that max-tolerance graphs are NP-hard
to recognize. On the positive side, the maximum clique problem can be
solved in polynomial time in this class of graphs.
(This is joint work with Jan Kratochvil, Katharina Lehmann and Amarendran
Subramarian.)
Jan Kratochvil (Charles University, Prague): Polygon-circle graphs
Polygon-circle graphs are intersection graphs of polygons inscribed to a
circle. They generalize well known and studied classes of graphs - circle
graphs, circular-arc graphs and chordal graphs. Though their recognition
has been announced polynomial time solvable in 1990, the announced paper
has never been published and the problem is regarded as open by the
community. We show that recongition becomes NP-hard if the polygons are
restricted to bounded number of corners. We also give asymptotically tight
bound for the maximum number of corners required for representing a
polygon-circle graph on $n$ vertices.
(This is a joint work with Martin Pergel.)
Gelasio Salazar (University Sant Louis Potosi): Improving the
bounds on crossing number
The crossing number problem is one of the key problems in geometric
optimization. But its specific hardness lies in the fact that even for
small graphs and some simple graph classes the exact crossing number
is not known. Recently we managed to improve the lower bounds for meshes,
complete graphs and complete bipartite graphs.
Marcus Schaefer (DePaul University, Chicago): Crossing Number
versus Odd Crossing Number
Abstract: The crossing number of a graph is the minimum number of edge
intersections in a plane drawing of a graph, where each intersection is
counted separately. If instead we count the number of pairs of edges that
intersect an odd number of times, we obtain the odd crossing number. We
show that there is a graph for which these two concepts differ, answering
a well-known open question on crossing numbers. To derive the result
we study drawings of maps (graphs with rotation systems). It was
conjectured that odd crossing number equals crossing number, since this is
true for the base case; that is, if the odd crossing number of a graph is
0, so is the crossing number. We also give a very simple new proof of this
old result of Hanani and Tutte, and show how to apply our proof technique
to obtain several other results, including a simplified proof of the
result by Pach and Toth that the crossing number is bounded by the square
of the odd crossing number.
(This is joint work with Michael Pelsmajer, and Daniel Stefankovic.)
Pavel Valtr (Charles University, Prague): Extremal problems for
geometric graphs
Geometric graphs are graphs given with explicit straight-line drawing in
the plane. We will discuss extremal problems on the maximum number of
edges of geometric graphs with forbidden configurations, such as $k$
pairwise crossing edges, $k$ pairwise noncrossing edges etc. We improve
several previously known bounds and survey open questions in the area.
(The talk is partly based on joint works with Geza Toth and Jan Kyncl.)
|