Introduction

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

1 2 3 4 5 6 7 8 9 ... 13

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 = (L₁, L₂, E) be a two-layered hierarchical graph, and D(G) be a drawing of G, where u L_1, N_uis the set of vertices on layer L₂that is adjacent with a vertex u on layer L₁. A barycenter value of vertex u on layer L₁ is defined as the average value of all of its adjacent vertices' positions. Formally, the barycenter value of a vertex u on layer L₁ 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 R². 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 G_rev (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 R². In other words, a drawing of a hierarchical graph is a mapping of all vertices, v

V, points in R² 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 L_i and u L_j. 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|² | |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 L₁, L₂, L₃, … L_k such that (u, v)

V, where u

L_i, u

L_j, 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, w₁ and w₂ are weight functions on V. For every v V:

. Let C^*, C^*₁, and C^*₂ be optimum covers of G with respect w, w₁ and w₂

(Yehuda, 2000).

Median value of a vertex: Let G = (L₁, L₂, E) be a two-layered hierarchical graph, u L₁ and u L₂, and pos₁, pos₂ be the ordering of layers L₁ and L₂ respectively. The median value of a vertex u on L₁ is described as follows:

If adjacent vertices of the vertex u on layer L₁ are vertices u_1,u₂, …,u_non layer L₂, with pos (u₁) < pos (u₂) < …. < pos (u_n), where n is the number of vertices on layer L₂, the median value of vertex u on layer L₁ , denoted as med(u), is chosen as a median of all the positions of vertices u on layer L₂that are adjacent to vertex u on layer L₁. (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 g₁,g₂,….,g_n. Compute layouts l₁,l₂,….,l_n 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 g₁,g₂,….,g_n. Compute layouts l₁,l₂,….,l_n for these graphs such that layout l_i is similar to l_i+1

Ordering of vertices on a layer in a k-layered hierarchical graph: Let D(G) be a drawing of hierarchical graph G, V_i = {v₁,…., v_ni} are vertices of layer i. V_i  (1, . . ., n_i) is defined as a bijective function that maps vertices on layer i to the drawing D such that pos(v_i) < pos(v_j) if x(v_i) < x(v_j) 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 = (L₁, L₂, E) be a two-layered hierarchical graph, u, v L₁, pos₁, pos₂ be the ordering of layers L₁ and L₂ respectively, and pos₂ 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:

Ratio bound of h = opt_h(G, pos₂) / LB (G, pos₂) (4)

(3) & (4) => Ratio bound of h = opt_h(G, pos₂) /

Where opt_h(G, pos₂) 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 R²:

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 = (L₁, L₂, E), (u, u)

E where u

L₁and u

L₂. 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 = (L₁, L₂, E) be a two-layered hierarchical graph, pos₁, and pos₂ 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, L₁, L₂ are layers of G, and pos₁ and pos₂ are orderings

of layers L₁ and L₂_, respectively. L₂ is held fixed, and let opt(G, pos₂) be the minimum number of crossings of drawing D of G with respect to pos₂. Find the minimum number of edge crossings of layer L₁. Formally:

Let G = (L₁, L₂, E) be a two-layered hierarchical graph with an ordering pos₂_,find an ordering pos₁ such that crossing (G, pos₁, pos₂) = opt(G, pos₂)
Hence, the minimum number of crossings of a drawing D of G:

opt(G, pos₂) = min {cross(G, pos₁, pos₂)| pos  S_|V1| } (1)

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

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

C_uv =

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 C_uv is 1 and C_vu is 6.

Figure 9. The crossing number c_uv = 1

Figure 10. The crossing number c_uv = 1

Figure 11. The crossing number c_vu= 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 L₁.

Formally: crossing (D(G), pos₁, pos₂) = (2)

Combine (1) and (2): opt(G, pos₂)

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, pos₂) = (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.

1 2 3 4 5 6 7 8 9 ... 13

Introduction

Definitions of Terms

Ratio bound of h = opth(G, pos2) / LB (G, pos2) (4)

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

Ratio bound of h = opt_h(G, pos₂) / LB (G, pos₂) (4)

(3) & (4) => Ratio bound of h = opt_h(G, pos₂) /