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. We start with the history of the simplest and best known 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.
Vladlen Koltun, UC Berkeley
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 a subquadratic number of cuts. 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 these distances have been asked (and, at least partially, answered). 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)
Vladim Lozin, RUTCOR, Rutgers University
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.
Rados Radoicic, MIT, Cambridge
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.
Next: Call for Participation
Workshop Index
DIMACS Homepage