Better see my NEW PAGES,

   hurry, or you miss it...

    My Math and CS research topics in brief

I started my math research with work on intersection and contact representations of graphs, and their recognition complexity. Namely, my master thesis was about contact graphs of curves. I was working on contact graphs of various kinds (of curves, line segments, balls) together with Jan Kratochvíl during my Master and Ph.D. studies at Charles University. Then I changed a school, and continued for my Ph.D. at Georgia Tech, working with Robin Thomas on planar covers of graphs.
After that I participated in the Special year on Combinatorics and Optimization at The Fields Institute in Toronto, Canada. I continued some previous work on contact graphs, and I studied other problems concerning graph embeddings and crossing number (with Bruce Richter).
Since life is a change, I moved to New Zealand then in 2000, where I learned structural matroid theory from Geoff Whittle. That became my prominent research area -- I have focused on matroid structure theory, and on related complexity questions mainly concerning the branch-with measure.
Now, back in the Czech republic, I have got a regular academic position with a teaching load, and I have less and less time for my research. Still, I continue active research in the areas of matroid complexity questions, various structural width parameters, and the graph crossing number.

See below for more details...

    Crossing number of graphs

The crossing number of a graph G, denoted by cr(G), is defined as the smallest possible number of edge-crossings in a drawing of G in the plane. A graph G is crossing-critical if cr(G-e)<cr(G) for all edges e of G.
(I have got to crossing number problems thanks to Bruce Richter during my stay at the Fields Institute.)

(2000) We have proved that crossing-critical graphs have "bounded path-width" (by a function of the crossing number), which roughly means that such graphs are made up of small pieces joined in a linear way on small cut-sets. Equivalently, a crossing-critical graph cannot contain a subdivision of a "large" binary tree.
This result was conjectured earlier by Salazar, and the positive answer may possibly help in a search for infinite families of crossing-critical graphs for a particular crossing number.

(2001) There is also a new construction of crossing-critical graphs that we use to find crossing-critical graphs with rather large binary trees. This construction is significantly different from all other known constructions, and it leads to crossing-critical graph that become planar after deleting one edge.
(2003) More research on the crossing number of graphs, and mainly on the structure of crossing-critical graphs has been done together with G. Salazar.
There is a construction of crossing-critical graphs in the projective plane with arbitrarily high degrees. In a new NP reductions we show that crossing number remains NP-hard even for cubic simple graphs. This, in particular, implies that the minor-monotone version of crossing number is NP-hard to compute.

(2006-7) New research directions towards efficient approximations of the crossing number for graphs which are "close to planarity", together with G. Salazar.
Namely we have shown a Delta-approximation for the crossing number of almost-planar graphs, and Delta^2-approximation for the crossing number of toroidal graphs.
(2008) Extensions of efficient approximations to apex graphs (with Markus Chimani and Petra Mutzel).

(2008) Some new results on the structure of crossing-critical graphs (with Salazar), and some new constructions.

    Matroids / graphs and width parameters

The basic question in matroid representations is to say what matroids are representable over a given field. That includes finding forbidden minors for representability, or to characterize representable matroids in terms of other representations. So far, the excluded minors are known only for GF(2), GF(3), and GF(4) representable matroids. In particular, it is interesting to look on representations of matroids over so called "partial fields". (Examples like regular or near-regular matroids, etc.)
Similarly to structural graph theory, it appears that the key concepts to the above problems are matroid connectivity and branch-width / tree-width. We have worked on these concepts together with Geoff Whittle.

(2001) We have shown that a minor-minimal bridge for a k-separation in a matroid has always bounded size if and only if k<=2 or the matroid is represented over a finite field. The technique of "bridging separations" is often used with matroid representations.

(2002-05) We have also worked on the computational aspects of matroid branch-width. We have shown that many hard problems become solvable in polynomial time for matroids of bounded branch-width that are represented over finite fields. In particular, these include branch-width itself, all problems definable in the monadic second-order logic, and problems related to the Tutte polynomial, etc. (It turns out that most of analogous stuff translates from graphs of bounded tree-width to matroids of bounded branch-width when these are represented over a fixed finite field.)
On the other hand, the above mentioned problems remain hard for matroids represented over any infinite field even when branch-width is at most 3 (cf. so called spikes).

(2006-07) The algoritmic ideas of matroid branch-width can be nicely applied to computation of graph rank-width and optimal rank decompositions (with S. Oum).
(2008) A new "parse tree" characterization of rank-decompositions of graphs and related dynamic algorithms (with Robert Ganian), equivalent to an algebraic characterization by Courcelle and Kante [WG'07].

    Matroid computation -- MACEK

Unlike graphs, matroids are very hard to imagine (or to draw a picture) and to apply even simple operations to them. On the other hand, many structural matroid results require us to do "small-case" analysis in an addition to the general proof.
(2002) For those reasons we have developed a software package MACEK for structural computations with matroids represented over finite (partial) fields. The package is free (under GPL), so if you are interested in matroids, do not hesitate to try it. (Version 1.0.)
(2003-05) Many new useful functions are being added to MACEK in the development branch 1.1.x, which is now available in the stable branch 1.2.x. (It includes abstract isomorphism, connectivity, and representability testing.)
(2007-?) New development is being planned...

    Intersection and contact graphs

Given an arbitrary set family M, the intersection graph of M is defined as follows: The graph G=G(M) has vertex set V(G)=M, and edge set E(G)={ {A,B}\subseteqM: A\not=B, A\cap B\not=\emptyset}.
Informally, the vertices of the intersection graph are the sets from M, and the edges of G connect intersecting pairs of these sets. In such situation, the family M is called an intersection representation of the graph G.

Unlike for intersection graphs, there is no general definition of a contact graph. However, if the sets (objects) in our family are defined in certain geometrical terms, then we may say what it means that two objects "touch" each other (or are in a "contact"). In such case, a contact representation is defined as an intersection representation in which the special objects are not allowed to cross, but only to touch each other.

(1994-98) We worked on curve and line-segment contact graphs, mainly on related algorithmic and recognition problems (inspired by research of Jan Kratochvil). Among other, We have proved that their recognition is polynomial for planar triangulations while the same question is NP-complete for general planar graphs.
We have also considered the recognition problem for unit-ball contact graphs in general dimensions. The case of dimension 2 was previously considered by Kirkpatrick and Breu. We can prove NP-hardness of the recognition in dimensions 3,4,8, and 24. However, we are not able to come out with a general reduction. (That is likely related to difficult problems of sphere packings and kissing number.)

    Planar covers of graphs - Negami's conjecture

We say that a given graph G has a finite planar cover if there exists a finite planar graph H and a mapping from V(H) onto V(G) such that it maps the neighbors of each vertex bijectively onto the neighbors of its image. For example, a regular dodecahedron double-covers Petersen graph.

In 1988, Negami published a conjecture saying that a graph has a finite planar cover if and only if it is embeddable in the projective plane. One direction is clear, each projective-planar graph has a double planar cover.
To prove the other direction, it is enough to show that each of 32 connected forbidden minors for the projective plane has no finite planar cover. Partial results are known due to Archdeacon, Negami, Fellows, and me (the graph K44-e, 1996). From the list, only one case remains unsolved nowadays - the graph K_1,2,2,2.

It is tempting to say that Negami's conjecture is almost proven, but that is not quite accurate for two reasons. First, there are five other graphs in the list of all minor-minimal nonprojective graphs, which are reduced to K_1,2,2,2 by the YDelta-transformation. And second, the arguments outlined above do not imply that these six graphs are the only possible counterexamples to the conjecture.
(1999) R. Thomas and I proved that two of the remaining six unsolved graphs have no finite planar cover. Based on this result, we managed to prove that, modulo obvious constructions, there are at most 16 possible counterexamples to Negami's conjecture. The conjecture is still open.