Interactive layout generation with a diagrammatic constraint language

The paper analyzes a diagrammatic reasoning problem that consists in findin g a graphical layout which simultaneously satisfies a set of constraints ex pressed in a formal language and a set of unformalized mental constraints, e.g. esthetic preferences. For this type of problem, the performance of a l ayout assistance system does not only depend on its use of computational re sources (algorithmic complexity) but also on the mental effort required to understand the system's output and to plan the next interaction (cognitive complexity). We give a formal analysis of the instantiation space of a weak ly constrained rectangle layout task and propose a measure for the cognitiv e complexity. It is discussed how the user's control of the presentation or der of the different constraint instantiations affects the cognitive comple xity.