PostScript is an amazing programming language for describing scalable graphics and interfaces! I especially enjoy the ability to very concisely represent information, using dedicated PostScript facilities to construct domain-specific languages, and I have used it to illustrate many situations that would otherwise be quite difficult to show.

I hope that an example can illustrate this point: In Volume 4 of The Art of Computer Programming, Donald Knuth explains how we can find kernels with maximum weight in C_{100}, the cycle graph with 100 nodes. In that example, the weight he assigns to each node is the Thue-Morse code, i.e., (-1)^ν, where ν is the number of occurrences of 1 in the binary encoding of the node number. So for example, the weight of node 2 is -1, and the weight of node 3 is 1.

We can easily determine the Thue-Morse weight of an integer in PostScript:

    /weight { 1 dict begin /nu 0 def
              { dup 0 eq { pop exit } if
                dup 1 and 1 eq { /nu nu 1 add def } if
                -1 bitshift } loop
              -1 nu exp end } bind def

Example: 8 weight ⇒ -1

Now, how might we compactly lay out the cycle graph with 100 nodes? Using PostScript lets us easily play with different layouts. For example, let us use r, u, l and d to move right, up, left and down, respectively:

     /instrs {
       { r r r r r r r r r r r r r r r r
                                       d
           l l l l l l l l l l l l l l
          d
           r r r r r r r r r r r r r r r
                                       d
         l l l l l l l l l l l l l l
        d
          r r r r r r r r r r r r r
                                    d
         l l l l l l l l l l l l l l l
         l u r  u l  u u u } } def

We can see what the described path looks like by interpreting this mini-language:

    30 dup scale
    1 15 translate

    /r { 1 0 translate } bind def
    /d { 0 -1 translate } bind def
    /l { -1 0 translate } bind def
    /u { 0 1 translate } bind def

    0.06 setlinewidth
    0 0 moveto

    gsave instrs { cvx exec 0 0 lineto } forall
    closepath stroke
    grestore

Now, we only have to draw the nodes themselves on top of this path. First, let us define which nodes are actually part of a kernel with maximum weight, found with the methods outlined by Knuth (operations on reduced and ordered Binary Decision Diagrams):

    /inkernel [101 { false } repeat] def

    [1 3 6 9 12 15 18 20 23 25 27 30 33 36 39 41 43 46 48 51 54 57 60 63
     66 68 71 73 75 78 80 83 86 89 92 95 97 99] {
        inkernel exch true put
    } forall

And now we can simply draw the nodes by interpreting the instructions again, and indicating whether a node is part of the kernel, and whether its weight is positive:

    /Palatino-Roman 0.4 selectfont

    0.04 setlinewidth
    1 1 instrs length {
        /num exch def
        newpath
        num weight -1 eq
          { -0.4 -0.4 0.8 0.8 4 copy
            inkernel num get { 0.8 } { 1 } ifelse gsave setgray rectfill grestore
            rectstroke
          }
          { 0 0 0.4 0 360 arc
            inkernel num get  { 0.8 } { 1 } ifelse gsave setgray fill grestore
            stroke
          }
        ifelse
        0 0 moveto num 5 string cvs dup stringwidth pop -2 div -0.12 moveto show
        instrs num 1 sub get cvx exec } for

In this case, I am using circles for nodes with positive weight.