joint work with Slawomir Lasota

Query Width is a complexity measure, like Tree Width, or Clique Width. The difference is that Tree Width or Clique Width measure the complexity of a graph, while Query Width measures the complexity of a graph whose nodes are linearly ordered (or organized in a tree, in the more general case). I will discuss where this notion comes from (our research on XPath), how it is related to the other measures (closely, with clique width) and what can be done in the future.