This page documents how KLay Layered implements label placement, port placement, and node sizing.

Contents

Introducing Important Stuff

When talking about label placement and node sizing, it helps to know what the two actually are. Let's start with node sizing:

On to port placement:

And finally label placement:

Relationship Between Label Placement, Port Placement, and Node Sizing

At first glance, label placement and node sizing are two separate problems. However, out of the three types of labels we currently support, two have considerable influence on the size of nodes (node labels and port labels, but you already figured this out yourself). Well, in fact, that's not completely true. It's not the labels that influence the size of nodes, it's the placement of labels. And if we didn't care for readability, the placement wouldn't influence node size at all. But we do. Take this simple example:

The two nodes have two labeled ports each. Let's assume port positions to be fixed, and labels to be placed inside the nodes. Clearly, the left node is too narrow for the port labels to be placed without overlaps. If the labels are to be placed without overlaps, we need to increase the width of the node. Label placement influences node sizing.

Matters get more complicated if we allow port positions to be changed. If the western port is moved upwards and the eastern port downwards, the labels don't overlap anymore. Thus, label placement also influences port placement.

Just how much and in what ways the three influence each other is one source of complexity. One important task in implementing label placement, port placement, and node sizing is to determine the cases where we simply give up. If the user gives us fixed node sizes and fixed port positions, he cannot expect us to find an overlap-free label placement if port labels are to be placed inside the node.

Anatomy of a Node

When it comes to label placement and node size calculations, we can think of a node as having the following anatomy:

The insets area is used as follows:

• If port labels are placed inside a node, the insets area is used to place them.
• If node labels are placed inside a node at one of the four sides (as apposed to centered), the insets area is used to place them.

The child area is what is left of the node with the insets subtracted. With the SizeConstraint.CHILD_AREA, KLay Layered can compute the child area and return it. This makes it easy to use in cases where the child area of the node is going to be used for displaying graphics or further text. If a minimum size is set on the node and the options SizeConstraint.MINIMUM_SIZE and SizeConstraint.MINIMUM_SIZE_ACCOUNTS_FOR_INSETS are set, the minimum size will effectively only apply to the child area. Thus, KLay Layered can be told to ensure that the child area of a node has a certain size, whatever space the port labels and node labels require.

Limitations of Our Algorithms

We cannot support everything – actually, many combinations of label placement, port placement, and node sizing constraints don't even make much sense. So here's a (possibly still growing – science can only do so much...) list of things we don't support:

• More than one port label. Who would want to have more than one anyway?
• More than one node label. More than one label can usually be combined into a single KLabel object if the relative locations of the labels don't change.

General Approach

The general approach to solving label placement, port placement, and node sizing follows the following general pattern:

1. Place port labels
2. Place ports
3. Reserve space for node labels
4. Resize node
5. Place node labels

Each task will be described in more detail in the following.

Place Port Labels

Each port's labels are placed. The exact placement strategy may differ depending on node sizing and port placement constraints. The easiest way of placing port labels, however, is not to care about other constraints just yet.

Place Ports

All ports are placed. If node sizing constraints allow for it, ports are placed in a way that ensures that port labels don't overlap each other. This is only possible, though, if SizeConstraint.PORT_LABELS is set. In all other cases, we can only hope that the result is free of overlaps.

This step also computes the insets of the node.

Reserve Space for Node Labels

If the node label is to be placed inside of the node, the insets are adjusted to reserve space for it. The label cannot be placed just yet since we don't necessarily know the node's final size at this point. Only node labels placed at the top left of the node could be placed, since the node's size doesn't influence them.

Resize Node

With the insets calculated, this step resizes the node, ensuring that the node size constraints are met. If the node is to have a minimum size, it may be resized accordingly, for instance. If ports are to be taken into account for the size calculation, the node size is adjusted to accommodate for its ports.

Place Node Labels

Once the node size is calculated, node labels are placed.

Port Placement

The only cases where we even have to talk about the placement of ports are those where their position is not fixed. That more or less leaves us with the three port constraints FREE, FIXED_SIDES, and FIXED_ORDER. The first is reduced to the second by assigning ports to the eastern or western side depending on the number of incoming and outgoing edges (if a port has more outgoing edges than incoming ones, it can be regarded as an output port). The second is reduced to the third during crossing minimization, in an attempt to find an order that will yield the fewest amount of edge crossings. Thus, the only case of real interest to us is FIXED_ORDER.

Port placement is influenced in the following ways by label placement and node sizing:

• Label Placement: Ports should be placed in a way that avoids label overlaps.
• Node Sizing: If node sizing doesn't pay any attention to ports, port placement options may be severely restricted.