Algorithmus von Walker

Der Algorithmus von Walker ist ein Reglement zum Zeichnen von Bäumen in der Graphentheorie.

Der Algorithmus basiert auf der geschichteten Zeichnung des Baumes (Layered Drawings). Dabei ergibt sich die Y-Koordinate eines jeden Knoten des Baumes direkt aus der Tiefe des Knotens. Dadurch muss bei diesem Algorithmus nur die X-Koordinate des jeweiligen Knotens in der Zeichnung bestimmt werden.

Die Laufzeit des Algorithmus ist, anders als ursprünglich vermutet, nicht linear, sondern quadratisch abhängig von der Anzahl der Knoten. Es existiert jedoch eine Verbesserung des Algorithmus von Christoph Buchheim et al., der eine lineare Laufzeit ermöglicht.

Literatur

• John Q. Walker: A node-positioning algorithm for general trees. In: Software: Practice and Experience. Band 20, Nr. 7, 1. Juli 1990, ISSN 1097-024X, S. 685–705, doi:10.1002/spe.4380200705. 
• Christoph Buchheim, Michael Jünger, Sebastian Leipert: Improving Walker’s Algorithm to Run in Linear Time. In: Graph Drawing (= Lecture Notes in Computer Science). Nr. 2528. Springer, Berlin / Heidelberg 2002, ISBN 978-3-540-00158-4, S. 344–353, doi:10.1007/3-540-36151-0_32.