Graph Theoretic Concepts in Computer Science

This volume gathers the proceedings of the 36th International Workshop on Graph-Theoretic Concepts in Computer Science, known as WG 2010, held in Zaros on Crete, Greece, from June 28 to 30, 2010. Roughly 60 mathematicians and computer scientists attended from Australia, Canada, the Czech Republic, France, Germany, Greece, Hungary, Israel, Japan, the Netherlands, Norway, Poland, Switzerland, the United Kingdom and the United States.

The workshop has a long history. Since 1975 it has been held 21 times in Germany, four times in the Netherlands, twice each in Austria and France, and once each in the Czech Republic, Greece, Italy, Norway, Slovakia, Switzerland and the United Kingdom. Its purpose is to combine theory with practice, showing how graph theory can be used across different areas of computer science and drawing new graph-theoretic problems out of real applications. Speakers present emerging research and point out directions for future work, with a program that balances established researchers and younger scientists.

The Program Committee received 94 submissions, two of which were withdrawn before review. Each paper was reviewed by at least three members, averaging 4.5 reviewers, and 28 papers were accepted, an acceptance rate of about 30 percent. The editors note that the competition and limited schedule meant some rejected papers deserved acceptance.