Walker's algorithm

from Wikipedia, the free encyclopedia

The algorithm of Walker is a regulation for drawing trees in graph theory .

The algorithm is based on the layered drawing of the tree. The Y coordinate of each node in the tree results directly from the depth of the node. With this algorithm, only the X-coordinate of the respective node in the drawing has to be determined.

The running time of the algorithm is different than originally suspected, not linear but quadratic function of the number of nodes. However, there is an improvement to the algorithm by Christoph Buchheim et al. , which enables a linear runtime.

literature

  • John Q. Walker: A node-positioning algorithm for general trees . In: Software: Practice and Experience . tape 20 , no. 7 , July 1, 1990, ISSN  1097-024X , p. 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 ). No. 2528 . Springer, Berlin / Heidelberg 2002, ISBN 978-3-540-00158-4 , pp. 344-353 , doi : 10.1007 / 3-540-36151-0_32 .