### DIMACS Workshop on Geometric Graph Theory

#### September 30 - October 4, 2002 DIMACS Center, Rutgers University, Piscataway, New Jersey

Organizer:
Janos Pach, City College and Courant Institute, New York, pach@cims.nyu.edu
Presented under the auspices of the Special Focus on Computational Geometry and Applications.

### Abstracts:



James Abello, AT&T and DIMACS

Title: The majority rule and geometry

We will present results relating the transitivity of the
majority rule to the realizability of Goodman-Pollack
Sequences. The methods rely on a local min-max property
that is satisfied by maximal chains under the weak Bruhat
Order of the symmetric group.

Helmut Alt, Freie Universitat, Berlin

Title: The complexity of (un)folding

We consider the problem of unfolding linkages of rigid line segments by a
continuous nonintersecting motion in the plane and in three dimensions.
More generally, we consider the problem whether it is possible to reach
one configuration from another one.  The problem is nontrivial even for
trees in two dimensions since it is known that not all configurations can
be unfolded.  We will show that the reachability problem is decidable,
for arbitrary graphs in arbitrary dimensions.  Furthermore, it turns out
that deciding unfoldability even for trees in two dimensions and chains in
three dimensions is PSPACE-hard. (With Christian Knauer, G|nter Rote, Sue
Whitesides)

Boris Aronov, Polytechnic University, Brooklyn

Title: Incidences problems: some history and new developments

We discuss so-called "incidence" problems in which one is
interested in the maximum number of incidences possible
between a set of points and a set of curves in two and
higher dimensions.

version of the problem, namely that of lines and points
in the plane. We discuss several methods used for solving
these problems and their applicability in other contexts.
The state of the art has evolved to the point where the
original question has a "one-line" solution, but several
extensions remain quite challenging and open. We describe
the tools needed to construct upper bounds for lines and
circles, in dimensions two and higher.

Imre Barany, Renyi Institute and Univ. College London

Title: The minimum area convex lattice n-gon

Let $A(n)$ be the minimum area of convex lattice $n$-gons where the
lattice is the usual lattice of integer points in $R^2$. G. E. Andrews
proved in 1963 that $A(n) > cn^3$ f or a suitable positive $c$. We show
that $\lim A(n)/n^3$ exists. Our computations suggest that the value of
the limit is very close to 0.0185067. (This is joint work with Norihide
Tokushige)

Peter Brass, City College, New York

Title: Convex Geometric Hypergraphs

Graphs with a cyclic ordering on the vertices are known as convex
geometric graphs'; they model the combinatorial structure of systems of
sides and diagonals in a convex  polygon, and can thus be interpreted
as geometric graphs whose vertex set is in convex position. The
forbidden-substructure extremal theory of convex geometric graphs has
already been studied in a number of papers, it is much nearer to classical
extremal graph theory than the similar extremal theory for geometric
graphs, although it also shows some surprising differences.

In this talk I will present a similar Tur\'an-type extremal theory for
convex geometric hypergraphs, that is, hypergraphs on a cyclically ordered
vertex set, or equivalently systems of $k$-gons selected from the vertices
of a convex $n$-gon. Again special cases of such systems have been
previously studied, e.g. the maximum-area triangles contained in a convex
$n$-gon. I will also give one new application.

Timothy M. Chan, University of Waterloo

Title: An algorithmic application of the concave-chain decomposition

It is well-known that the $(\le k)$-level in an arrangement of lines can
be decomposed into $k+1$ concave chains.  This observation has yielded
simple proofs on the complexity of the $(\le k)$-level, and more recently
(in conjunction with crossing arguments in geometric graphs), has led to
Dey's result on the $k$-level in 2-d. Here, we look at an interesting
algorithmic application of the concave-chain decomposition: solving linear
programs with $\le k$ violations in 2-d.

In considering the 3-d problem, we also show that the $(\le k)$-level
in an arrangement of planes can be covered by $O(k)$ concave surfaces.
This new observation can be proved using the chromatic number of an
intersection graph of pseudo-disks.

Tamal K. Dey, Ohio State University, Columbus

Title: Counting triangulations using crossings in geometric graphs

Given a set of n labeled points in S^d, how many combinatorially different
geometric triangulations for this point set are there? A very simple
argument with geometric crossings gives an upper bound of n^\floor{d/2}+1
on the logarithm of this number. For odd d, this is better than Kalai's
n^\ceil{d/2}\log n bound. For even d, we show that this bound is  actually
n^{d/2} matching the known lower bound by Kalai if we assume that any
simplicial complex embedded in S^d has at most O(n^{d/2}) simplices.
We conjecture that this assumption is true and provide some evidence in
its support.

Adrian Dumitrescu, University of Wisconsin, Milwaukee

Title: On the Maximum Multiplicity of Some Extreme Geometric
Configurations in the Plane

We investigate what is the the maximum number of times a certain extreme
geometric configuration can occur in an $n$-element point set in the
plane. In particular we are interested in minimum (resp. maximum) geometric
matching and minimum (resp. maximum) geometric spanning tree. We give
upper and lower bounds on the maximum multiplicity of these
configurations.

Hubert de Fraysseix, EHESS, Paris

Title: Automorphisms and Isometries of Graphs

Given a graph $G$ on $n$ vertices, we define a distance $d$ among its
vertices such that the graph can be isometrically embedded in $\bbbr^n$.
This particular distance has the following { \em reconstructibility}
property: up to an isomorphism, one can reconstruct the graph $G$ from the
distances among its vertices.  It easily follows that the automorphisms
of $G$ are in a one to one correspondence with the isometries of its
embedding.

The computation of the embedding mainly consists in computing an
orthonormal basis associated with the eigenvalues of the inner product
matrix $\omega$ defined by the distance $d$.  As the isometries operates
transitively on the proper subspaces of $\omega$, the complexity of
finding isometries ({\em i.e.} the automorphisms of $G$) is very much
related to the multiplicity of the eigenvalues of $\omega$.

We get similar problems  as in the graph spectral analysis approach to
study automorphisms.  But in this geometric framework many of the spectral
properties of $\omega$  can be easily interpreted, which may help to
improve our knowledge of graph automorphisms. (Joint work with Patrice
Ossona de Mendez)

Subir Kumar Gosh, Tata Institute of Fundamental Research

Title: Recognizing visibility graphs of simple polygons

We first introduce visibility graphs of polygons in the context of robot
path planning. Then we present four necessary conditions for recognizing
visibility graphs of simple polygons and conjecture that these conditions
are sufficient. We show that visibility graphs of simple polygons do not
possess the characteristics of a few special classes of graphs (perfect
graphs, circle graphs, etc.). Finally, we discuss the issues involved in
reconstructing simple polygons from visibility graphs.

Van Vu Ha, University of California, Davis

Title: The geometry of random objects

We study  some geometric properties of random objects. Here is an
example: "How many lines does one need to separate a set of n random
points in a unit square (so that between every two points there is a
line)?"  Our main tool is a combinatorial lemma which is of independent
interest.

Robert Jamison, Clemson University

Title: Bigraceful labelings of trees

Let $X$ be any finite set of points in the real Euclidean plane. A {\em
direction tree} on $X$ is a tree whose vertices are the points of $X$ and
whose edges all have different slopes. Here the slope of an edge is the
slope of the line determined by its endpoints. It is a consequence
(cf. {\em Discrete Comput Geom} {\bf 2}(1987), 249-254) of a celebrated
result of Peter Ungar ({\em JCTA} {\bf 33}(1982), 343-347) that any finite
set of noncollinear (i.e., not all on a line) points determine a
direction tree.

This talk is concerned with the structure of direction trees for a
special family of configurations --- the bicolumnar arrays $BC(s,t)$,
which consist of $s+1$ evenly spaced points on a vertical line and $t+1$
evenly spaced points on a parallel line.  It turns out that the
realization of a tree as a direction tree of $BC(s,t)$ avoiding the
infinte slope corresponds to a vertex labeling  which is similar in some
ways to the well-known notion of graceful labeling. Here negative labels
are also allowed but must alternate with positive labels. Sums, rather
than absolute values of differences, are the induced edge labels and must
be distinct.  In contrast to the known results in the graceful case, it
turns out that some trees do not have bigraceful labelings.

However, every tree lies in a bigraceful tree, and, on the other hand,
every tree is a subtree of a tree that is not bigraceful.  We will examine
some constructions for bigraceful trees as well as some proof techniques
for showing a tree is not bigraceful.

Martin Juvan, University of Ljubljana

Title: Planar graphs without cycles of specific lengths

A graph $G$ is $d$-degenerate if every subgraph $H$ of $G$ contains
a vertex of degree at most $d$ in $H$. For example, planar graphs are
5-degenerate. It is easy to see that planar graphs without cycles of
length 3 are 3-degenerate. It is also known that the same holds for
planar graphs without cycles of length 5. In the talk I will try to
convince the audience that planar graphs without cycles of length 6
are also 3-degenerate. Some connections with list colorings of planar
graphs will also be mentioned. (This is a joint work with G. Fijav\v{z},
B. Mohar, and R.  \v{S}krekovski.)

Mikio Kano, Ibaraki University, Hitachi

Title: Alternating no-crossing geometric paths that cover red and blue
points in the plane

For given red and blue points in the plane, we want to cover all these
points with alternating geometric paths of the same length without
crossings.  We give a complete solution to this problem. Namely, if the
length of the path is at most 12, then a trivial necessary condition is
sufficient, and if the length of the path is at least 13, then there exist
configurations which has no such coverings.

In order to solve this problem, we obtain the following balanced
partition theorem: For given $kg+(k+1)h$ red points and $(k+1)g+kh$
blue points in the plane, there exists a subdivision $X_1 \cup ... \cup X_g \cup Y_1 \cup ... \cup Y_h$ of the plane into g+h disjoint convex
polygons such that every $X_i$ contains $k$ red points and $k+1$ blue
points and every $Y_j$ contains $k+1$ red points and $k$ blue points.
(Joint work with Zvi Schur, Micha Perles and Horst Martini)

Gyula Karolyi, Eotvos University, Budapest

Title: Geometric graph Ramsey numbers

A geometric graph is a graph drawn in the plane with straight line
segments as edges connecting vertices that are assumed to be in general
position. Given two outerplanar graphs $G$ and $H$, we denote by
$R_g(G,H)$ the smallest integer $R$ with the property that any complete
geometric graph with at least $R$ vertices whose edges are colored by red
and blue contains either a non-crossing subgraph isomorphic to $G$ all
whose edges are red or a non-crossing subgraph isomorphic to $H$ all whose
edges are blue. We denote by $R_{cg}(G,H)$ the corresponding number
when we restrict our attention to convex geometric graphs, that is,
geometric graphs whose vertex sets are convexly independent.

In this talk we survey what is known about these numbers when the
graphs $G$ and $H$ belong to some restricted classes of outerplanar
graphs like paths, stars or cycles. In particular, denoting a
cycle of length $k$ by $C_k$, we prove that
$$R_g(C_3,C_k)=R_{cg}(C_3,C_k)=3k-3\ ,$$ a result obtained together with
Vera Rosta.

Stephen G. Kobourov, University of Arizona,
Tucson

Title: Simultaneous embedding of planar graphs

Traditional representations of graphs and their duals suggest the
requirement that the dual vertices should be placed inside their
corresponding primal faces, and the edges of the dual graph should cross
only their corresponding primal edges. We consider the problem of
simultaneously embedding a planar graph and its dual on a small integer
grid such that the edges are drawn as straight-line segments and the only
crossings are between primal-dual pairs of edges. We provide an $O(n)$
time algorithm that simultaneously embeds a 3-connected planar graph and
its dual on a $(2n-2)\times (2n-2)$ integer grid, where $n$ is the total
number of vertices in the graph and its dual.

Another related problem is that of embedding several different planar
graphs (with or without a mapping between the vertices) on the integer
grid. We present new results for both variants of the problem and several
algorithms for some special cases (paths, caterpillars, and outerplanar
graphs). For example, given a planar graph $G$ with $n$ vertices, we
provide an algorithm to find a straight-line planar embedding of $G$ on an
$O(n^3)\times O(n^3)$ grid, so that the vertices of $G$ lie in general
position. We then show how this algorithm can be used for obtaining a
simultaneous then show how this algorithm can be used for obtaining a
simultaneous embedding of two planar graphs when one of the graphs is
outerplanar.

Title: Cutting cycles of lines in space

Given a collection of polygons in 3-space, the classical problem of
hidden-surface removal calls for determining which parts of the
polygons are visible from a given viewpoint. Some hidden-surface
removal algorithms rely on sorting the polygons by depth, which
requires that no subcollection should form a cycle'. Thus a strategy
for cutting polygons into pieces that form no cycles is needed. This
gives rise to the problem of estimating how many such cuts may be
necessary, and how many are always sufficient. Partially confirming a
long-standing conjecture, we show that all triangular cycles', which
are cycles that are formed by triples of lines, can be eliminated with

Joint work with Boris Aronov and Micha Sharir.

Alexander Kostochka, University of Illinois, Urbana

Title:  Coloring intersection graphs of geometric figures with no large
cliques

For a class $L$ of graphs and an integer $k\geq 2$, let $f(L,k)$
(respectively, $g(L,k)$) denote the maximum chromatic number of a graph
$G\in L$ with clique number at most $k$ (respectively, with girth greater
than $k$). We survey estimates on $f(L,k)$  and $g(L,k)$ when $L$ consists
of intersection graphs of a special kind. In particular, we consider
intersection graphs of intervals on the plane, chords of a circle, boxes,
etc.

Jan Kratochvil, Charles University, Prague

Title: A survey of new results and old problems in geometric intersection
graphs

Intersection graphs of geometric flavor, especially in the euclidean
plane, have been intensively studied both for their practical applications
and interesting structural properties. Recently, substantial progress was
achieved namely in the question of computational complexity of recognizing
string graphs, i.e., intersection graphs of curves. I will survey the new
development of the area as well as some pertaining open problems.

Yaakov Kupitz, Hebrew University, Jerusalem

Title: Extremal problems on the diameter graph of a finite set in $R^d$

A set $V=\{v_1, v_2, ..., v_n\}$ of $n$ distinct points in Euclidean
$d$-space $R^d$ determines ${n\choose 2}$ distances. Some of these
distances may be equal. Many questions concerning the distribution of
E.g., how often can a particular distance (say, one) occur and, in
particular, how often can the largest (resp., the smallest) distance
occur? In this talk I will consider mainly the largest distance, i.e.,
the diameter. (Joint work with Zvi Schur, Micha Perles and Horst Martini)

Title: Gearing Optimization

We consider an optimization problem arising in machine-tool
construction. It deals with optimizing the structure of a gearbox, which
is normally represented by a graph. The edges of such graph correspond to
pairs of gear-wheels and the vertices stand for velocities. There is a
designated input vertex and a certain subset of output vertices. The
problem is to create the graph with a given number of output vertices
minimizing the total number of vertices and edges of the graph. We present
an efficient solution to this problem in the special case of regular
graphs.

Hiroshi Maehara, University of Ryukyus, Okinawa

Title: A condition for the union of spherical caps to be connected

Let ${\cal C}$ be a finite family of a spherical caps of various sizes on
a sphere in 3-space. A cap $C\in {\cal C}$ is called extremal if there is
a great circle $g$ such that the centers of those caps that intersect $C$
lie in the same side of $g$, allowing some of them lie on $g$. We prove
that if ${\cal C}$ contains no extremal cap, then the intersection graph
of the caps in ${\cal C}$ is connected, and if furthermore every cap is
smaller than a hemisphere, then the intersection graph is 2-connected. We
also show that analogous assertions are no longer true in higher
dimensions.

Jiri Matousek, Charles University, Prague

Title: Problems and results on pair crossing number

The crossing number of a graph G is the minimum number of edge crossings
in a drawing of G in the plane (edges can be drawn as arbitrary curves),
while the pair-crossing number is the minimum number of pairs of edges
that cross. A challenging open problem is whether the crossing number is
always equal to the pair-crossing number. In the absence of any progress
on this question, one can attempt to bound the crossing number at least by
some function of the pair-crossing number. Pach and T\'oth proved a bound
of O(k^2), where k is the pair-crossing number; this can be slightly
improved to O(k^2/log k) using a lemma of Schaefer and
\v{S}tefankovi\v{c}.  If one assumes that the drawing is monotone (every
edge is an x-monotone curve), then the bound can be improved to
O(k^{5/3}). These results have been obtained at a student research
seminar led by Pavel Valtr and the speaker. One of the significant lower
bounds for the crossing number is const.(bw(G)^2 - \sum_{v\in V(G)}
deg(v)^2), where bw(G) is the bisection width of G (the smallest number of
edges that must be removed to split G into two parts of roughly equal
size). By combining known techniques, mainly due to Leighton, Rao, and
Bhatt, a slightly weaker lower bound, with an extra factor
polylogarithmic in |V(G)|, can be proved for the pair-crossing number. As
a consequence, we obtain that for graphs where k significantly exceeds the
sum of squared degrees, the crossing number is at most O(k log^4 k). It
seems that the next step in this approach is to understand better the
crossing number of graphs with high degrees; for example, is there a good
approximation algorithm?

Sean McGuinness, Umea Universitet

Title: Bounding the chromatic number of intersection graphs of arcwise
connected sets in the plane

There are a number of open problems concerning finding a bound for the
chromatic number an intersection graph as function of its clique
number(size of largest clique).  Such problems include $L$-graphs(the
intersection graph of $L$-shapes), and the intersection graph of line
segments in the plane.

It is a surprisingly hard problem to find a bound on the chromatic
number of these graphs even in the triangle-free case (ie. clique number
=3D 2).  We shall discuss a more general type of problem which involves
the (triangle-free) intersection graph of arcwise connected sets in the
plane.  For such intersection graph of arcwise connected sets in the
plane.  For such graphs, it can be shown that the chromatic number is
bounded by a constant independent of the sets chosen, given that there is
a closed Jordan curve which intersects each of the sets in a particular
fashion.  This result has some interesting consequences eg. for the
(triangle-free) intersection graphs of unbounded arcwise connected sets
in the plane, where it can be shown that such graphs have bounded
chromatic number provided that the intersection of any two sets in the
family is also arcwise connected.  For example, this applies to the
intersection of rays in the plane.

Using the Jordan curve result one can also show that for an
(triangle-free) intersection graph $G$ of arcwise connected sets in the
plane(with certain restrictions), provided the chromatic number of $G$ is
large enough, there is a collection of 4 or 5 sets which 'surround' a
subcollection of sets whose corresponding intersection graph has chromatic
number bounded below by some fraction of the chromatic has chromatic
number bounded below by some fraction of the chromatic number of $G$, and
this fraction is independent of the sets chosen.

Bojan Mohar, University of Ljubljana

Title: The genus of graphs on a fixed nonorientable surface

Let S be a nonorientable surface. A collection of pairwise noncrossing
simple closed curves in S is a blockage if every onesided simple closed
curve in S crosses at least one of them. Robertson and Thomas conjectured
that the orientable genus of Let S be a nonorientable surface. A
collection of pairwise noncrossing simple closed curves in S is a
blockage if every onesided simple closed curve in S crosses at least one
of them. Robertson and Thomas conjectured that the orientable genus of any
graph G embedded in S with sufficiently large face-width is roughly''
equal to one half of the minimum number of intersections of a blockage
with the graph. The conjecture was disproved by Mohar and replaced by a
similar one. In the talk, it will be shown that both of these conjectures
hold up to a constant error term: For any graph G embedded in S, the
orientable genus of G differs from the conjectured value at most by
$O(g^2)$, where $g$ is the genus of S. This result will be included into a
more general framework of genus computation in minor closed families.
Part of the presentation is a joint work with Lex Schrijver.

Janos Pach, Renyi Institute and City College, New York

Title: Crossroads in Flatland - Toward a theory of geometric graphs

In the traditional areas of graph theory (Ramsey theory, extremal
graph theory, random graphs, etc.), graphs are regarded as
abstract binary relations. The relevant methods are often
incapable of providing satisfactory answers to questions arising
in geometric applications. Geometric Graph Theory focuses on
combinatorial and geometric properties of graphs drawn in the
plane by straight-line edges (or, more generally, by edges
represented by simple Jordan arcs). It is a fairly new discipline
abounding in open problems, but it has already yielded some
striking results that have proved to be instrumental for the
solution of several important problems in combinatorial and
computational geometry. These include the k-set problem, proximity
questions, bounding the number of incidences between points and
lines, designing various efficient graph drawing algorithms, etc.
In this lecture we try to give a taste of some of the basic
questions and results of this emerging theory.

Micha Perles, Hebrew University, Jerusalem

Title: Simple spanning forests in geometric graphs

Let G be a gg (=geometric graph) of order n. Denote by e-
(=e-(G)) the number of missing edges of G.
If e-=n-1, then it may happen that every simple spanning subgraph
of G has an isolated vertex. (Examples: G = K(n-1) plus an isolated
vertex, or G = CK(n) with n-1 boundary edges deleted. Here
CK(n) = complete convex gg of order n.)
If e-=n-2, then G has a simple spanning tree of diameter <= 3.
If e-<n/2, then every disjoint union of any number of stars of
total order n is isomorphic to a simple spanning subgraph of G. If G
is convex and e-<n/2, then every caterpillar of order n is
isomorphic to a simple spanning subgraph of G.
For a=>2, b=>2, denote by St(a,b) the disjoint union of a
star of order a and a star of order b. Define for a=>2, b=>2:

f(a,b) = min{e-(G): G is a gg of order a+b that has no simple
subgraph of type St(a,b)}.

f_c(a,b) is defined in the same way, with "gg" replaced by
"cgg" (= convex gg).
Results:
f(a,a) = [4/3*a] for all a=>2.
f_c(a,a) = f(a,a)   for a = 2,3,4,6;
f_c(a,a) = f(a,a)+1    otherwise.
f(2,3)   = f_c(2,3)   = 3                 ;
f(2,n-2) = f_c(2,n-2) = [[2/3*n]] for n=>6.
(Here [[x]] stands for the smallest integer => x.)
f(3,4)   = f_c(3,4)   = 5                 ;
f(3,n-3) = f_c(3,n-3) = [[3/4*n]] for n=>8.
f_c(a,b) => f(a,b) => [[4/3*(a+b)]] for 2<=a<b. Equality
holds when a and b are both not divisible by 3, and in some other
cases as well.
If G is convex, of order n=>5, and e-= 2, then every tree of
order n is isomorphic to a simple spanning subgraph of G.
If G = CK(n) with one boundary edge deleted (n=>3, e-=1),
then G has no simple hamiltonian circuit.
If e-= 0 (i.e., G is complete), then every outerplanar graph
of order n is isomorphic to a simple spanning subgraph of G. If G is
convex, then every simple subgraph of G is outerplanar.

Rom Pinchasi, MIT, Cambridge

Title: Almost planar topological graphs

We discuss some extremal problems concerning topological
graphs. Let G be a topological graph. For any constant r, if G
does not have r edges incident to the same vertex which cross the
same edge, then |E(G)|=O(n). The same holds if G does not have r
edges, each of which crosses the same three edges.
This is a joint work with Janos Pach and Micha Sharir.

Richard Pollack, Courant Institute, NYU

Title: On the Betti numbers of semi-algebraic sets

A classic result in real algebraic geometry due to Oleinik-Petrovsky,
Thom, and Milnor, bounds the topological complexity  (the sum of the Betti
numbers) of basic semi-algebraic sets. These bounds are used in many
applications -- for instance, for proving tight lower bounds on the
complexity of several problems in computer science. Over the past few
years there have been several improvements and generalizations of this
bound due to Basu, Basu-Pollack-Roy, and Pollack-Roy. In particular, it is
now possible to prove better bounds on the individual Betti numbers of
semi-algebraic sets rather than their sum. The talk will be a survey of
these results and their geometric applications to configurations of
finite point sets in $R^d$, geometric transversal theory, and
generalizations of arrangements of segments and their higher dimensional
analogues.

Title: Geometric graphs with no self-intersecting cycle of length 4

The fundamental question of extremal graph theory is to determine the
maximum number ex(n, H) of edges in an H-free graph on n vertices, where
H is a class of so-called forbidden subgraphs. We consider a geometric
analogue of this question when H consists of all self-intersecting
straight-line drawings of a fixed graph K. In other words, what is the
maximum number ex'(n, K) of edges in a geometric graph on n vertices
if it contains no self-intersecting copy of K? Clearly, ex'(n, K) \geq
ex(n, K). The question is interesting when K is a bipartite planar
graph. Pach, Pinchasi, Tardos and T\'oth recently studied the case when K
= P_3.  We discuss the case when K = C_4. We prove that ex'(n, C_4) =
O(n^{8/5}). This is a joint work with Rom Pinchasi.

Paul Seymour, Princeton University

Title: Strong perfect graph theorem

Claude Berge proposed the conjecture in 1961 that, in every graph with no
odd hole or odd antihole, the number of colours needed to properly colour
the graph equals the size of the largest complete subgraph.  (A
"hole" means an induced subgraph which is a cycle of length >= 4, and an
"antihole" is the same in the complement graph.) This has become one of
the most well-known and popular open problems in graph theory. Most
attempts on it have been based on linear programming methods, studying the
properties of a minimal counterexample; they go a long way, but appear
eventually to get stuck. Recently, however, a new approach was initiated
by Conforti and Cornuejols, an attempt to actually find explicit
constructions for all the graphs not containing odd holes or antiholes,
and checking directly that they satisfy Berge's conjecture.  I am happy to
report that this works. In joint work with Maria Chudnovsky, Neil
Robertson and Robin Thomas, we have been able to carry out the
Conforti-Cornuejols program, and thereby prove Berge's conjecture.

Farhad Shahrokhi, University of North Texas

Title: On pseudo-transitive graphs

The notion of orderings'' naturally arise in many problems of
combinatorial and computational geometry. The underlying structures often
exhibit some sort of weak transitivity'' properties.  However, in many
cases, the crucial properties of these problems cannot be categorized by
the classical theory of partially ordered sets. Motivated by geometric
considerations, we introduce the concept of pseudo-transitivity'' in
directed acyclic graphs.

A directed  graph $G=(V,E)$ with no cycles is pseudo-transitive with
respect to a given subset of edges $A$, if $ab\in A$ and $bc\in E$ implies
that $ac\in E$. We  derive several algorithmic results for computing
longest chains and also present an approximate chain-antichain covering
theorem valid in large classes of pseudo-transitive graphs. The results
unify many geometric concepts and have important applications and
consequences.

Micha Sharir, Tel Aviv University and Courant
Institute

Title: New bounds on incidences and related problems

We present several recent results, in which new bounds are derived
for the number of incidences between points and curves in two and
three dimensions, as well as several related results, where these
new bounds are applied. We also review the recent history of the
incidence problem and its relatives.

We first consider the problem of cutting circles and pseudocircles
in the plane (closed Jordan curves, each pair of which intersect
at most twice) into pseudo-segments, that is, arcs with the property
that each pair of them intersect at most once. We derive new bounds
for the number of cuts, which improve a general previous bound, due
to Tamaki and Tokuyama.

Combining these results with Sz\'ekely's technique, which is based on
crossing numbers of graphs, and with dual space partitioning techniques,
we obtain improved bounds for incidences between points and circles,
between points and parabolas, between points and pseudo-circles, and
between points and graphs of polynomials of fixed maximum degree.

Similar bounds are also obtained for the complexity of many faces
in arrangements of curves of these classes. Improved bounds are also
derived for levels in such arrangements.

We also discuss algorithms for computing incidences and many faces
in such arrangements. The algorithms make use of a new duality
transform (related to an earlier one due to Goodman) between
points and pseudolines. This transform has also several other
applications.

We next consider the problem of incidences between points and curves
in three dimensions. This area has not been studied before, and we
obtain a variety of new bounds for incidences between points and lines,
between points and equally-inclined' lines, between points and circles,
and between points and certain kind of helices.

Finally, there are several additional applications of the new bounds.
We mention two of them: A new lower bound for the number of distinct
distances in three dimensions, and improved upper bounds for the
number of simplices spanned by a point set in three or four dimensions
and congruent to a given simplex.

Obviously, all of this will not fit into a single talk. In fact, we
will most likely not even reach the middle of this abstract. The
purpose of the abstract is to provide extra information for
interested people.

Shakhar Smorodinsky, Tel Aviv University

Title: On conflict free coloring of discs in the plane

Motivated by frequency assignment problems in cellular networks, we
study problems of the following flavor: Given a set $P$ of $n$ points
in the plane, what is the minimum number $f(n)$ such that one can
assign colors to points of $P$, using a total of at most $f(n)$ colors
and such that the coloring have the following property (which we refer
to as Conflict Free Coloring): For any disc $d$ in the plane, with
nonempty intersection with $P$, there is at least one point $p$ of $P$
inside $d$ which has a unique color among the points inside $d$.  We
show that $f(n) = O(\log n)$. This is asymptotically tight in the
worst case.

Joint work with Guy Even, Zvika Lotker and Dana Ron (Tel-Aviv University).

Joel Spencer, Courant Institute, NYU

Title: Crossing numbers for random graphs

As the random graph $G(n,p)$ evolves the crossing number increases. We
explore that time when a positive proportion of pairs of edges must
cross. We explore the usual crossing number, the rectilinear crossing
number and pairwise crossing numbers, with quite different results in the
three cases. (joint work with Geza Toth)

Daniel Stefankovic, University of Chicago

Title: Deciding string graphs in NP

A string graph is an intersection graph of a set of curves in the
plane. The recognition problem (given a graph G, is G a string graph?) was
shown to be decidable only recently by Pach, Toth and Schaefer, S. I will
survey techniques and results which were used by Schaefer, Sedgwick, S. to
show that the recognition problem is NP. These include results of
Plandowski and Rytter on word equations with lengths and the theory of
normal coordinates.

William Steiger and Mario Szegedy, Rutgers University

Title: Long x-monotone paths in line arrangements

We show how to construct an arrangement of $n$ lines having
an x-monotone path of length
$\Omega(n^2/C^{\sqrt(\log{n})})$, $C>1$ a suitable constant.

Laszlo A. Szekely, University of South Carolina,
Columbia

Title: Crossing numbers and biplanar crossing numbers

A {\it biplanar drawing of a graph} $G$ means partitioning the edge set of
the graph into two graphs, $G_1$ and $G_2$, and drawing $G_1$ and $G_2$ in
two disjoint planes. A graph is {\it biplanar}, if it admits a biplanar
drawing without edge crossings, i.e. the graph has thickness at most 2
(Beineke 1997). Biplanar drawings have obvious significance for VLSI,
since such a drawing has physical realization using two sides of a chip,
when vertices are present on both sides of the chip (Owens 1970). Unlike
planarity, testing  graph  biplanarity is NP-complete (Mansfield 1983).

In this talk we study the biplanar crossing number $cr_2(G)$ of the
graph $G$.  Formally, $cr_2(G)=\min cr(G_1)+cr(G_2)$, where $G_1 \cup G_2 =G$. The positive results: We show that $cr_2(G)\leq (3/8)cr(G)$. Using
this result recursively, we bound the thickness by
$\Theta(G)=2+O(cr_2(G)^{.4057})$.

Negative result: for any size exceeding a certain linear threshold,
there exists a graph $G$ of this size, which simultaneously has the
following properties: $cr(G)$ is roughly as large as it can be for graphs
of that size, and $cr_2(G)$ is as small as it can be  for graphs of that
size. This is a joint work with Ondrej Sykora and Imrich Vr to.

Endre Szemeredi, Rutgers University

Title: An elementary method in combinatorial number theory

A simple combinatorial idea from combinatorial number theory
will be discussed. We present two applications: bounding
the size of a set of integers not containing (a) an arithmetic
progession of length 3, (b) two elements whose sum is a perfect
square.

Gabor Tardos, Renyi Institute, Budapest

Title: Geometric graphs without short self-intersecting paths

It is well known, that a planar graph with n vertices has at most 3n-6
edges. In other words a geometric graph with more than 3n-6 edges has two
intersecting edges, and (not hard to see) it also contains a
self-intersecting path. What if we are looking for a short
self-intersecting path? Tight bounds are presented for the maximum number
of edges in a geometric graph avoiding a self-intersecting path of length
3, while for longer paths we give partial results, among them a
construction of a graph with a superlinear number of edges avoiding
self-intersecting paths of any fixed constant length.

Much of this research is joint work with Janos Pach, Rom Pinchasi and
Geza Toth.

Takeshi Tokuyama, Tohoku University, Sendai

Title: How to reform a terrain into a pyramid

Given nonnegative valued functions $\rho$ and $\mu$ in one or two
variables, we consider the optimal pyramid maximizing the total parametric
gain of $\rho$ against $\mu$. The pyramid can be considered as the optimal
unimodal approximation of $\rho$ relative to $\mu$, and can be applied to
data segmentation in image processing and data mining. We design efficient
algorithms for several cases. (Joint work with Jinhee Chun, Naoki Katoh)

Geza Toth, Renyi Institute, Budapest

Title: How many drawings are there?

A graph is called a {\em string graph} if its vertices can be represented
by continuous curves (strings'') in the plane so that two of them cross
each other if and only if the corresponding vertices are adjacent. Let
$\cal S$ denote the property of being a string graph.

We prove that from the $2^{{n\choose 2}}$ labeled graphs on $n$
vertices, roughly $2^{{3\over 4}{n\choose 2}}$ are string graphs.

We will also consider several related results, generalizations, and
consequences. Joint work with Janos Pach.

Pavel Valtr, Charles University, Prague

Title: Turán-type Results for Convex Geometric Graphs

We study Turán-type extremal questions for graphs with an
additional cyclic ordering of the vertices, i.e.~for (combinatorial
equivalence classes of) convex geometric graphs. If a suitably defined
chromatic number of the excluded subgraph is bigger than two then the
results on convex geometric graphs resemble very much the classical
results from the Turán theory.  On the other hand, in the bipartite
case we show some surprising differences, in particular for trees and
forests. For example, the Turán function of some convex geometric
forests is of the order $\Theta(n\log n)$, a growth rate that does not
occur in the Tur\'an theory. As a consequence, we obtain a new proof of
the $O(n\log n)$ bound on the maximum number of unit distances between
vertices of a convex $n$-gon. (Joint work with Peter Brass and Gyula
Károlyi)

Uli Wagner, ETH Zurich

Title: Rectilinear crossing number of complete graphs

We prove a lower bound of 0.3288{n \choose 4} for the rectilinear crossing
number $\overline{\textrm{cr}}(K_n)$ of a complete graph on $n$ vertices,
or in other words, for the minimum number of convex quadrilaterals in any
set of $n$ points in general position in the Euclidean plane. As we see
it, the interesting aspect is not so much the concrete numerical
improvement over earlier bounds, as the novel method of proof, which is
not based on bounding $\overline{\textrm{cr}}(K_n)$ for some small $n$.



Next: Call for Participation
Workshop Index
DIMACS Homepage
Contacting the Center