Seminars and Colloquia by Series

Augmenting undirected node-connectivity by one - Part II

Series
Graph Theory Seminar
Time
Thursday, March 29, 2012 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Laszlo VeghCollege of Computing, Georgia Tech
In the node-connectivity augmentation problem, we want to add a minimum number of new edges to an undirected graph to make it k-node-connected. The complexity of this question is still open, although the analogous questions of both directed and undirected edge-connectivity and directed node-connectivity augmentation are known to be polynomially solvable. I present a min-max formula and a polynomial time algorithm for the special case when the input graph is already (k-1)-connected. The formula has been conjectured by Frank and Jordan in 1994. In the first lecture, I presented previous results on the other connectivity augmentation variants. In the second part, I shall present my min-max formula and the main ideas of the proof.

Augmenting undirected node-connectivity by one

Series
Graph Theory Seminar
Time
Thursday, March 8, 2012 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Laszlo VeghCoC, GT
In the node-connectivity augmentation problem, we want to add a minimum number of new edges to an undirected graph to make it k-node-connected. The complexity of this question is still open, although the analogous questions of both directed and undirected edge-connectivity and directed node-connectivity augmentation are known to be polynomially solvable. I present a min-max formula and a polynomial time algorithm for the special case when the input graph is already (k-1)-connected. The formula has been conjectured by Frank and Jordan in 1994. In the first lecture, I shall investigate the background, present some results on the previously solved connectivity augmentation cases, and exhibit examples motivating the complicated min-max formula of my paper.

Triangle-free families of segments with large chromatic number

Series
Graph Theory Seminar
Time
Thursday, February 16, 2012 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Arkadiusz PawlikJagiellonian University, Krakow, Poland
We consider intersection graphs of families of straight line segments in the euclidean plane and show that for every integer k, there is a family S of line segments so that the intersection graph G of the family S is triangle-free and has chromatic number at least k. This result settles a conjecture of Erdos and has a number of applications to other classes of intersection graphs.

Circuits in medial graphs and bipartite partial duals

Series
Graph Theory Seminar
Time
Thursday, November 17, 2011 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Iain MoffattUniversity of South Alabama
A classical result in graph theory states that, if G is a plane graph, then G is Eulerian if and only if its dual, G*, is bipartite. I will talk about an extension of this well-known result to partial duality. (Where, loosely speaking, a partial dual of an embedded graph G is a graph obtained by forming the dual with respect to only a subset of edges of G.) I will extend the above classical connection between bipartite and Eulerian plane graphs, by providing a necessary and sufficient condition for the partial dual of a plane graph to be Eulerian or bipartite. I will then go on to describe how the bipartite partial duals of a plane graph G are completely characterized by circuits in its medial graph G_m. This is joint work with Stephen Huggett.

Optimal decompositions of quasi-line trigraphs

Series
Graph Theory Seminar
Time
Tuesday, October 25, 2011 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Andrew KingSimon Fraser University
Chudnovsky and Seymour's structure theorem for quasi-line graphs has led to a multitude of recent results that exploit two structural operations: compositions of strips and thickenings. In this paper we prove that compositions of linear interval strips have a unique optimal strip decomposition in the absence of a specific degeneracy, and that every claw-free graph has a unique optimal antithickening, where our two definitions of optimal are chosen carefully to respect the structural foundation of the graph. Furthermore, we give algorithms to find the optimal strip decomposition in O(nm) time and find the optimal antithickening in O(m2) time. For the sake of both completeness and ease of proof, we prove stronger results in the more general setting of trigraphs. This gives a comprehensive "black box" for decomposing quasi-line graphs that is not only useful for future work but also improves the complexity of some previous algorithmic results. Joint work with Maria Chudnovsky.

Structure of crossing-critical graphs

Series
Graph Theory Seminar
Time
Friday, September 23, 2011 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Zdenek DvorakCharles University, Prague, Czech Republic
A graph G is k-crossing-critical if it cannot be drawn in plane with fewer than k crossings, but every proper subgraph of G has such a drawing. We aim to describe the structure of crossing-critical graphs. In this talk, we review some of their known properties and combine them to obtain new information regarding e.g. large faces in the optimal drawings of crossing-critical graphs. Based on joint work with P. Hlineny and L. Postle.

Points covered by many simplices

Series
Graph Theory Seminar
Time
Friday, September 16, 2011 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Daniel KralCharles University, Prague, Czech Republic
Boros and Furedi (for d=2) and Barany (for arbitrary d) proved that there exists a constant c_d>0 such that for every set P of n points in R^d in general position, there exists a point of R^d contained in at least c_d n!/(d+1)!(n-d-1)! (d+1)-simplices with vertices at the points of P. Gromov [Geom. Funct. Anal. 20 (2010), 416-526] improved the lower bound on c_d by topological means. Using methods from extremal combinatorics, we improve one of the quantities appearing in Gromov's approach and thereby provide a new stronger lower bound on c_d for arbitrary d. In particular, we improve the lower bound on c_3 from 0.06332 due to Matousek and Wagner to more than 0.07509 (the known upper bound on c_3 is 0.09375). Joint work with Lukas Mach and Jean-Sebastien Sereni.

Roman domination on 2-connected graphs

Series
Graph Theory Seminar
Time
Thursday, April 28, 2011 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Chun-Hung LiuMath, GT
A Roman dominating function of a graph G is a function f which maps V(G) to {0, 1, 2} such that whenever f(v)=0, there exists a vertex u adjacent to v such that f(u)=2. The weight of f is w(f) = \sum_{v \in V(G)} f(v). The Roman domination number \gamma_R(G) of G is the minimum weight of a Roman dominating function of G. Chambers, Kinnersley, Prince and West conjectured that \gamma_R(G) is at most the ceiling 2n/3 for any 2-connected graph G of n vertices. In this talk, we will give counter-examples to the conjecture, and proves that \gamma_R(G) is at most the maximum among the ceiling of 2n/3 and 23n/34 for any 2-connected graph G of n vertices. This is joint work with Gerard Jennhwa Chang.

Control of Multi-Robot Networks

Series
Graph Theory Seminar
Time
Thursday, April 21, 2011 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Magnus EgerstedtECE, GT
Arguably, the overarching scientific challenge facing the area of networked robot systems is that of going from local rules to global behaviors in a predefined and stable manner. In particular, issues stemming from the network topology imply that not only must the individual agents satisfy some performance constraints in terms of their geometry, but also in terms of the combinatorial description of the network. Moreover, a multi-agent robotic network is only useful inasmuch as the agents can be redeployed and reprogrammed with relative ease, and we address these two issues (local interactions and programmability) from a controllability point-of-view. In particular, the problem of driving a collection of mobile robots to a given target destination is studied, and necessary conditions are given for this to be possible, based on tools from algebraic graph theory. The main result will be a necessary condition for an interaction topology to be controllable given in terms of the network's external, equitable partitions.

Pages