Browse Prior Art Database

Algorithm to Count Line Crossings in a Leveled Graph

IP.com Disclosure Number: IPCOM000112751D
Original Publication Date: 1994-Jun-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 4 page(s) / 142K

Publishing Venue

IBM

Related People

Evans, DH: AUTHOR [+3]

Abstract

An algorithm is represented for optimizing arc crossings in a leveled graph that is A log A (where A is the number of arcs) and does not test and count each arc crossing individually. By taking advantage of the geometry in a leveled graph, an algorithm has been constructed that counts the arc crossings "in bulk"; that is, it does not examine the crossing of individual arcs. Instead, the geometry of a leveled graph is first utilized to determine which arcs must cross, and then a structure is created to manipulate the counts of arcs (and their sums) that impinge on the nodes.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 40% of the total text.

Algorithm to Count Line Crossings in a Leveled Graph

      An algorithm is represented for optimizing arc crossings in a
leveled graph that is A log A (where A is the number of arcs) and
does not test and count each arc crossing individually.  By taking
advantage of the geometry in a leveled graph, an algorithm has been
constructed that counts the arc crossings "in bulk"; that is, it does
not examine the crossing of individual arcs.  Instead, the geometry
of a leveled graph is first utilized to determine which arcs must
cross, and then a structure is created to manipulate the counts of
arcs (and their sums) that impinge on the nodes.

      The idea behind utilizing geometry to determine arc crossings
is to classify the kinds of arc crossings that can occur when
examining a pair of nodes on adjacent levels.  Assuming that each arc
consists of a single straight segment between a pair of nodes, it
turns out there are only two possible kinds of crossings given that
the nodes all lie on levels, and in the following, the two kinds of
arc crossings are defined and their use explained.

      The exemplary graph above is a two-level graph consisting of
levels L1 and L2 to illustrate the first type of arc crossing.  Nodes
are shown in lower-case letters.  For convenience, an arc is assumed
between every node on L1 and every node on L2.  When there is one or
more arcs between the node pair being considered, each such arc is
considered as a "pair arc" from the top level node.

      The algorithm works by making a single pass (from left to
right) pairing the first (left-most) node from L1 with the first node
from L2 <a, z>, the second nodes <b, x>, etc., until there are no
more nodes on one of the two levels.  Given this node pairing, arcs
can be represented by a pair <Pi, Pj> representing the positions of
their end nodes, where Pi is the position of the node on L1 and Pj is
the position of the node on L2.

      The algorithm only looks at an arc once as a "right-going arc";
that is, if in the arc's pair Pi < Pj, the arc is processed as a
right-going arc originating at Pi on L1.  If Pi > Pj, the arc is
processed as an arc originating at Pj on L2.  Therefore,  at the pair
<c, y> in the graph, all right-going arcs from node c cross the
right-going arcs from node y.  The right-going arcs from node c are
<c, v>, <c, u>, and <c, t>, and the right-going arcs from node y are
<d, y>, <e, y>, and <f, y>.  These can be counted by multiplying the
counts of right-going arcs from the two nodes.

      An "outstanding arc" is defined as an arc that originated from
the left of the current arc pair and ended to the right of the
current arc pair.  (These arcs are outstanding or introduced into the
computation from looking at an earlier node pair.)

      Thus, when looking at the pair <c, y>, any arc from a node in
the set {a, b} on L1 to nodes in the set {v, u, t} on L2 are
outstanding arcs from L1.  Similarly, arcs from the...