Ana səhifə

# Introduction

Yüklə 3.14 Mb.
 səhifə 4/13 tarix 24.06.2016 ölçüsü 3.14 Mb.

## Definitions of Terms

Acyclic graph: An acyclic graph is a simple graph that has no cycles.

Adjacent vertices: Two vertices a and b are adjacent if they are connected by an edge E (a, b).

Adjacent matrix: Let G (V, E) be a graph, and |V| x |V| matrix M. An adjacent matrix M is defined as follows:

Approximation algorithm: A design and analysis approach for solving combinatorial optimization problems such as NP-complete or NP-hard problems. The goal of approximation algorithms is to discover the lower bound of polynomial time computation.

Barycenter value of a vertex in a two-layered graph drawing: Let G = (L1, L2, E) be a two-layered hierarchical graph, and D(G) be a drawing of G, where u L1, Nu is the set of vertices on layer L2 that is adjacent with a vertex u on layer L1. A barycenter value of vertex u on layer L1 is defined as the average value of all of its adjacent vertices' positions. Formally, the barycenter value of a vertex u on layer L1 can be defined as follows:

avg(u) = (1/ deg(u)) (Battista et al., 1999)

where deg(u) is the degree of vertex u.

Complete graph: A complete graph is a simple graph such that each pair of vertices is connected by an edge.

Crossing number of a drawing: The crossing number of a drawing is the number of edge crossings in a drawing, excluding vertex intersections. Figure 2 shows that there is 1 crossing between the edges 2 and 3 but there is no crossing between edges 1 and 3, though 1 and 3 intersect at the endpoint. The crossing number of a drawing is denoted as crossing (D (G)).

Figure 2. There is one crossing between edges 2 and 3

Crossing number of a drawing notation: To simplify computing the number of edge crossings of a drawing we will define an edge crossing as an integer. Let D (G) be a drawing of G and e and e are edges of D(G), crossing (e, e) = 1 if e crosses e, otherwise crossing (e, e) = 0. The edge crossing of a drawing can be denoted as follows:

crossing (D(G)) = crossing(e, e)

Curve: A curve δ is a continuous mapping to topological space S such that δ : I S, where I is an interval of R and S is the Euclidean plane R2. Figure 3 shows an example of a curve.

Cycle: A path in a graph that starts and ends at the same vertex.

Cycled graph: A graph that has one or more cycles.

Degree of a vertex: Let G be a simple graph, v V and e E. The degree of a vertex v in the graph G, denoted as deg(v), is the number of edges incident to that vertex.

Directed graph: A directed graph is a simple graph where an edge is assigned to an ordered pair of vertices. The first vertex of the ordered pair is called the tail of the edge, and the other is called the head. The direction of an edge in a directed graph drawing is represented by an arrow. A directed graph is denoted as G (V, A) where V is a set of vertices and A is a set of directed edges.

Directed acyclic graph (DAG): A directed graph that has no cycles.

Directed graph with cycles: Let G (V, A) be a directed graph. G has a cycle if R forms a one-way loop of edges. To remove the cycles, set R of edges will be reversed such that Grev (R) is acyclic. Reversing set R of edges to make G acyclic is denoted as a feedback set. The optimal solution to the feedback set problem is to choose a set R of edges so that |R| is minimized (Battista et al., 1999).

Drawing of a hierarchical graph: A drawing of a hierarchical graph G (V, E) is an embedding of G into R2. In other words, a drawing of a hierarchical graph is a mapping of all vertices, v V, points in R2 and all edges, e E, to Jordan arcs such that all the vertices belonging to a given layer lie on the same horizontal lines. A drawing of a G is denoted as D (G).

Dummy vertex: A vertex created in a process of removing edges that span more than one layer in a hierarchical graph, which makes the graph a proper hierarchical graph.

Edge spans more than a layer on layered hierarchical graph: Let G (V, E) be a k-layered hierarchical graph, and span (e) = (j – i) is the number of layers an edge spans, where e = (u, u), u Li and u Lj. An edge e spans more than one layer if j > (i + 1).

Feedback arc set: Let G= (V, A) be a simple directed graph. The feedback arc set (FAS) of G, denoted as R (G), is a set of edges (possibly empty) whose reversal makes G acyclic. A minimum feedback arc set of G, denoted as R * (G), is a FAS of minimum cardinality of r* (G). (Eades, Lin, & Smith, 1993)

Graph: A graph G consists of a set V of vertices and a set E of edges, where. Each edge has a pair of vertices referred to as its endpoints (West, 2001).

Graph density: Let G (V, E) be a graph, graph density is defined as a quotient of the number of edges in the graph and the maximal number of edges in the graph. Formally: D = |E| / |V|2 | |V| > 0, where |V| is the number of vertices and |E| is the number of edges in the graph.

HTTP client: A program that establishes a connection to a server for the purpose of sending an HTTP request (W3C, 1999).

HTTP request: An HTTP message sent by an HTTP client requesting that some operation be performed on some resource. Also, the act of sending such a message is termed making a request (W3C, 1999).

HTTP response: An HTTP message sent back to an HTTP client in response to a previous HTTP request (W3C, 1999).

Incident edges: An edge E is incident to its endpoints or vertices.

Incremental graph layout: Please see on-line dynamic graph layout.

Independent set: Two sets A and B are said to be independent if their intersection A ∩ B = Ø, where Ø is the empty set. For example, set (a, b, c) and (d, e) are independent, but set (a, b, c) and (c, d) are not. Independent sets are also called disjoint or mutually exclusive. Independent sets or disjoint sets are used in defining partite graphs (Weisstein, 2003).

Jordan arc: A Jordan arc is a subinterval (c, d) of a Jordan curve, where a ≤ b ≤ c ≤ d as shown in Figure 3.

J
ordan curve:
A curve is closed or a loop if I = (a, b), a ≠ b and δ (a) = δ(b). A Jordan curve is defined as a non-self-intersecting loop in a plane which divides the plane into two disjoint regional curves, the inside and the outside.

Figure 3. A Jordan curve

J2EE: Java 2 Platform Enterprise Edition Server Side that serves dynamic web pages like JSP and servlets.

HTTP: Hyper Text Transfer Protocol, which provides a communication interface between client and server.

K-partite graph: A k-partite graph is a simple graph G whose vertices are a union of k independent (possibly empty) sets of vertices such that no two vertices in the same set are adjacent (West, 2001). Figure 4 shows a two-partite, or bipartite, graph with two independent sets of vertices: (a, b, c) and (d, e, f, g, h).

Figure 4. A bipartite graph

K-layered hierarchical graph: A k-layered hierarchical graph is a k-partite graph G (V, E) in which V is partitioned into k partite sets L1, L2, L3, … Lk such that (u, v) V, where u Li, u Lj, and i < j. A k-layered hierarchical graph is drawn such that the vertices in a given layer are drawn on a horizontal axis and the edges are drawn as straight lines.

The height of a k-layered graph layout is the number of layers, which is k. The width of the layout is the number of vertices in the layer that has the most vertices. Figure 5 shows a drawing of a 4-layered hierarchical graph that has a height of 4 and a width of 5.

Figure 5. A 4-layered graph layout (Battista et al., 1999)

Lexicographic order: Where A(a, b) and B(a, b) are two ordered sets, the

lexicographic order of the Cartesian product of A x B is defined as follows:

(a,b) (a,b) iff a < a or a = a & b < b

Local ratio theorem: Let G (V, E) be a graph and w, w1 and w2 are weight functions on V. For every v V: . Let C*, C*1, and C*2 be optimum covers of G with respect w, w1 and w2 (Yehuda, 2000).

Median value of a vertex: Let G = (L1, L2, E) be a two-layered hierarchical graph, u L1 and u L2, and pos1, pos2 be the ordering of layers L1 and L2 respectively. The median value of a vertex u on L1 is described as follows:

If adjacent vertices of the vertex u on layer L1 are vertices u1, u2, …,un on layer L2, with pos (u1) < pos (u2) < …. < pos (un), where n is the number of vertices on layer L2, the median value of vertex u on layer L1 , denoted as med(u), is chosen as a median of all the positions of vertices u on layer L2 that are adjacent to vertex u on layer L1. (Battista et al., 1999).

Formally: med (u) = pos ()

If vertex u has no adjacent vertices then med(u) = 0.

Off-line dynamic graph layout: Given a sequence of n graphs g1,g2,….,gn. Compute layouts l1,l2,….,ln for these graphs such that

(1)

(2)

where is a deviation of all the layouts and is defined as layout quality based on the aesthetic criteria (Diehl & Gorg, 2002)

On-line dynamic graph layout: Given a sequence of n graphs g1,g2,….,gn. Compute layouts l1,l2,….,ln for these graphs such that layout li is similar to li+1

Ordering of vertices on a layer in a k-layered hierarchical graph: Let D(G) be a drawing of hierarchical graph G, Vi = {v1,…., vni} are vertices of layer i. Vi(1, . . ., ni) is defined as a bijective function that maps vertices on layer i to the drawing D such that pos(vi) < pos(vj) if x(vi) < x(vj) where pos is defined as an ordering of vertices on layer i in a given drawing D(G) and pos(v) is a position of a vertex v on layer i.

Given that u, v are vertices on layer i in a given drawing D(G), a binary relation < is defined as relative positions between vertices u and v such that u < v iff pos(u) < pos(v)

Path: A list of vertices of a graph where each vertex that has an edge connecting it to the next vertex.

Proper layered hierarchical graph: A layered hierarchical graph is proper if it has no edges that span more than one layer. Figure 6 shows a layered hierarchical graph that is not proper because two of its edges span more than one layer. To make a layered hierarchical graph proper, each edge in the graph that spans more than one layer is split into multiple edges by inserting dummy vertices into the layers. Figure 7 shows the layered hierarchical graph made proper by splitting the two edges that span more than two layers into multiple edges. Two new dummy vertices have been created on layer 2.

Figure 6. A layered hierarchical graph with edges spanning more than one layer

Figure 7. The layered hierarchical graph made proper by inserting dummy vertices
Ratio bound performance of one-sided crossing reduction heuristics: Let G = (L1, L2, E) be a two-layered hierarchical graph, u, v L1, pos1, pos2 be the ordering of layers L1 and L2 respectively, and pos2 be held fixed. If h is a heuristic for solving the one-sided crossing reduction problem, a ratio bound of heuristic h can be defined as follows:

### (3) & (4) => Ratio bound of h = opth(G, pos2) /

Where opth(G, pos2) is the minimum number of crossing produced by the heuristic h and is the trivial lower bound of the one-sided two-layered crossing reduction problem.

R-approximation algorithm: A polynomial-time algorithm that produces a solution at most or (at least) r times the optimum. (Rabani, 2003).

Simple graph: A simple graph is a graph that has no loop or multi edges.

TCP protocol: Transmission control protocol, which provides reliable communication between two computers, such as client and server.

The crossing number of a graph: Let G be a graph and D(G) a drawings of G. The crossing number of a graph is the minimum crossing number of any of its drawings in a plane R2:

crossing (G) = min {crossing (D(G) | D(G) is a drawing of G }

Two-layered hierarchical graph: A two-layered graph is denoted as a triple: G = (L1, L2, E), (u, u) E where u L1 and u L2. Figure 8 shows a two-layered hierarchical graph.

Figure 8. A two-layered hierarchical graph

The crossing number in a drawing of a two-layered graph: Let G = (L1, L2, E) be a two-layered hierarchical graph, pos1, and pos2 are orderings of layers 1 and 2 respectively, then cross (G, pos1, pos2) is defined as the crossing number in a drawing of G.

The crossing reduction problem of one-sided two-layered graphs: Let G be a bipartite graph, L1, L2 are layers of G, and pos1 and pos2 are orderings

of layers L1 and L2, respectively. L2 is held fixed, and let opt(G, pos2) be the minimum number of crossings of drawing D of G with respect to pos2. Find the minimum number of edge crossings of layer L1. Formally:

Let G = (L1, L2, E) be a two-layered hierarchical graph with an ordering pos2, find an ordering pos1 such that crossing (G, pos1, pos2) = opt(G, pos2)
Hence, the minimum number of crossings of a drawing D of G:

opt(G, pos2) = min {cross(G, pos1, pos2)| pos S|V1| } (1)

where Sn is symmetric group of all permutations on layer 1.

The crossing number of two vertices in a one-sided two-layered graph: Let G = (L1, L2, E) be a two-layered hierarchical graph, u, v L1 | pos(u) < pos(v), Cuv is defined as the crossing number of edges incident with u and edges incident with v.

Cuv =

Where inc(u) is a set of edges incident to vertex u.

It is known that the number of crossings between edges incident with vertex u and edges incident with v depends only relative positions of u and v and not on other vertices (Battista et al., 1999). As illustrated in Figures 9, 10, and 11 Cuv is 1 and Cvu is 6.

Figure 9. The crossing number cuv = 1

Figure 10. The crossing number cuv = 1

Figure 11. The crossing number cvu= 6

The crossing number in a drawing D of a one-sided two-layered graph G can be defined as the sum of the number of edge crossings of all the pairs of vertices on the layer L1.

Formally: crossing (D(G), pos1, pos2) = (2)

Combine (1) and (2): opt(G, pos2)

Trivial lower bound of one-sided two-layered graph crossing reduction problem: A trivial lower bound of the one-sided two-layered graph crossing reduction problem can be also defined as follows:

LB (G, pos2) = (3)

This trivial lower bound of the crossing reduction problem for a one-sided two-layered graph will be used to compute the efficiency of the heuristic.

Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©atelim.com 2016
rəhbərliyinə müraciət