This is TikiWiki v1.9.8 -Sirius- © 2002–2007 by the Tiki community Pon 23 of Jul, 2018 [02:08 UTC]

Workshop on Theory and Algorithmic Aspects of Graph Crossing Number

print pdf
Brno, Czech Republic, 21-22 August 2010,
a satellite workshop to MFCS & CSL 2010.


The purpose of this workshop is to bring together researchers interested in the algorithmic aspects of graph crossing number problems. During the last ten years or so, we have witnessed a growing interest in complexity and algorithmic issues around crossing numbers. On the complexity front, we have Grohe’s surprising result that CrossingNumber is fixed parameter tractable, followed up by the recent refinement by Kawarabayashi and Reed. On the more applied side, we have the algorithms implemented by Petra Mutzel and her research team that compute the exact crossing number of relatively large graphs. Then there is a recent series of specialized constant-factor approximation algorithms for the crossing number by Hlineny, Salazar, and Chimani. Yet another really surprising, exciting result is Cabello and Mohar’s proof that CrossingNumber is still NP-hard for nearly-planar graphs (that is, graphs with an edge whose removal leaves a planar graph).

We see this workshop as an opportunity to reflect on these developments, with an emphasis on the interplay between the theoretical and the algorithmical aspects of graph crossing numbers.

Invited speakers
Sergio Cabello, University of Ljubljana
Daniel Štefankovič, University of Rochester

Contributed talks

If you intend to contribute a talk, we strongly encourage you to help us with the organization and email a tentative title to Gelasio Salazar at his address gsalazar AT ifisica DOT uaslp DOT mx . The abstracts of workshop talks will be published as part of the MFCS - CSL conference proceedings. Due dates will be aligned with the conference due dates, so by emailing your intentions you will make sure to be notified about them.

Important dates
Important dates follow the MFCS 2010 deadlines. In addition, camera ready 1-page abstracts of your talks have to be submitted by August 8th.

June 15, 2010 Accomodation booking at reduced rate.
June 23, 2010 MFCS/CSL early payment deadline.
July 30, 2010 Workshop (TAAGCN) early payment deadline.
July 30, 2010 Camera ready 1-page abstracts submitted.
August 17, 2010 Workshop dinner menu selection closes.
August 21 - 22, 2010 Workshop on Theory and Algorithmic Aspects of Graph Crossing Number.
August 23-27, 2010 35th International Symposium on Mathematical Foundations of Computer Science
August 23-27, 2010 19th EACSL Annual Conference on Computer Science Logic

We refer you to the page Please note that the deadline for the discounted accomodation rate is June 15.

Friday, August 20, 2010
18:00 Informal arrival gathering at Výtopna restaurant. Directions are available from
Saturday, August 21, 2010
9:00 Registration.
9:30 Sergio Cabello: Crossing numbers of near-planar graphs
10:15 Coffee break
10:30 Petr Hliněný: Lower bounds on the crossing number of surface-embedded graphs I: Up to torus
10:50 Markus Chimani: Lower bounds on the crossing number of surface-embedded graphs II: Higher Surfaces
11:10 Break
11:20 Ondřej Pangrác: Colorings and crossings
11:40 Gelasio Salazar: Assigning weights to edges in nonplanar graphs to make them crossing-critical
12:00 Lunch break
14:00 Problem Session: Algorithmic approaches to the crossing number of near-planar graphs (Gelasio Salazar, Petr Hliněný)
19:00 Workshop dinner at the Monâme restaurant. Directions are available at
Sunday, August 22, 2010
9:00 Daniel Štefankovič: Variants of Crossing Numbers
9:45 Coffe break
10:00 Éva Czabarka: Analogues of crossing numbers
10:20 Mojca Bračič: Towards understanding a crossing lemma with generalized probabilities: Euler core of a graph
10:40 Break
10:50 Marián Klešč: Join products and Cartesian products of stars — crossing numbers
11:10 Drago Bokal: Divide et impera for crossing numbers: graph cuts and Cartesian products with trees
11:30 Lunch break
14:00 Problem Session: When does one bundle suffice and what can we do with it? (Drago Bokal)
19:00 Survivor's party.

All talks will be in the building of the Faculty of Informatics, University of Brno, Botanická 68a. See map.

Workshop dinner
So that the workshop dinner runs smoother, we are requested to select menus beforehand. All the participants joining us for dinner are kindly requested to register their wishes on a web form. If you do not manage to respond on the form by August 17, 2010, you are still very welcome to the dinner, but your food selection may be limited to the default choice of "Pizza, great variety (and good)."

Confirmed participants
  • Drago Bokal, University of Maribor, Slovenia,
  • Mojca Bračič, University of Maribor, Slovenia,
  • Markus Chimani, University of Jena, Germany,
  • Eva Czabarka, University of South Carolina, USA,
  • Gašper Fijavž, University of Ljubljana, Slovenia,
  • Petr Hlineny, Masaryk University Brno, Czech Republic,
  • Janja Jerebic, University of Maribor, Slovenia,
  • Marián Klešč, Technical University of Košice, Slovakia,
  • Ondrej Pangrac, Charles University Prague, Czech Republic,
  • Michael Pelsmajer, Illinois Institute of Technology, USA,
  • Gelasio Salazar, Autonomous University of San Luis Potosi, Mexico,
  • Laszlo Szekely, University of South Carolina, USA.

Registration to TAAGCN 2010 is through the MFCS & CSL site. Participants are encouraged to register both for our workshop and for the conference.

TAAGCN 2010 Organizing Committee

Technical assistant:

Technical issues
  • If you want to be notified about the changes of this page, please register your email with this site and make your username of the form GCN_Username. For instance, GCN_FjodorDostojevskij.

Created by: b:0; last modification: Friday 30 of July, 2010 [07:04:06 UTC] by b:0;

Powered by Tikiwiki Powered by PHP Powered by Smarty Powered by ADOdb Made with CSS Powered by RDF
RSS Wiki rss Articles RSS Image Galleries RSS File Galleries rss Calendars