Luatodonotes: Boundary Labeling for Annotations in Texts - Graph Drawing - page 76

Fig. 1. Screenshot of comments in a document in LibreOce 4.1.5
bend minimization. They also studied leaders that contain a diagonal part and
gave an O ( n 2 )-time algorithm for the one-sided case. This result was extended
by Bekos et al. [3] to more than one side. Recently, Kindermann et al. [10] gave
the first ecient algorithms for po -leaders that decide whether an instance with
labels on two adjacent, three, or four sides has a crossing-free solution (and, if
yes, compute one).
Boundary labeling for non-uniform labels is still largely unexplored. Bekos
et al. [4] showed that it is NP-hard to find a crossing-free labeling if the labels
have to be placed on two sides (or two stacks on the same side). Huang et al. [9]
considered a version of the problem that is always feasible: labels are placed into
the right margin or into both margins, which are not bounded from below or
above. For this model, opo -leaders, and labels of non-uniform size, they gave an
O ( n 3 )-time algorithm that minimizes the total leader length in the one-sided
case. For the two-sided case, they showed NP-hardness.
In this paper, we focus on comments for Latex documents. There are some
packages that support the placement of textual comments in the margin, namely
todonotes [12], fixme [16] and fixmetodonotes [2]. They have in common that
they use Latex's \marginpar command to print the note as soon as the corre-
sponding command is encountered in the source of the document. The drawback
of this approach is that the positions of the following comments are not known