This paper introduces a new graph problem to find an Optimal Euler Circuit (OEC) in an Euler graph. OEC is defined as the Euler circuit that maximizes the sum of contiguous costs along it, where the contiguous cost is assigned for each of the two contiguous edges incident to a vertex. We prove that the OEC problem is NP-complete. A polynomial time algorithm will be presented for the case of a graph without vertex of degree greater than 4, and for the general case, a 1/4-approximation polynomial time algorithm will be proposed.

Network topology has no direct effect on the correctness of network protocols, however, it influences the performance of networks and their survivability when they are under attack. Recent studies have analyzed the robustness of the Internet in the face of faults or attacks which may cause node failures. However, the effect of link failure or a series of link failures has not been extensively examined, even though such a situation is more likely to occur in the current Internet environment. In this paper, we propose an attack-and-failure graph model and practical techniques for attacking strategies against nodes, edges or paths in order to reflect real-life attack scenarios. The resiliency of Internet topologies is examined under the attacking strategies, with various metrics including path-failure ratio and "attack power," which is defined as the ratio of the failure to attack. The experiments reveal that "path-based" attacks can result in greater damage to the connectivity of a network than the other types of attack. Nonetheless, the effectiveness of an attack depends on the objective that the attacker wants to achieve through the attack. The proposed simple but formalized approach can be a springboard for developing more resilient Internet topologies in a variety of aspects.

In this paper, we present a novel forwarding scheme to enhance communication stability based on geographic routing in mobile ad hoc networks, which is called "Position-based Heuristic Forwarding" (PHF). For alternative solutions to traditional ad hoc routings, many geographic routing algorithms have been proposed. Most of the existing routings impose a certain restriction, planarity, on the graph structure of network for delivering messages to destination definitely. PHF achieves the guaranteed packet delivery over Unit Disk Graph, which is more widely employed graph model for the study of ad hoc networks. Accordingly, to eliminate the restriction of the routing algorithms enhances the probability to deliver messages successfully in networks with high nodes' mobility rate. In the simulation of PHF, we have evaluated the performance comparisons between PHF and its related work, Greedy Perimeter Stateless Routing (GPSR) and Dynamic Source Routing (DSR), which are the prominent geographic and conventional topology-based routing protocols, respectively. The results show that PHF provides higher packet delivery success rate indicating better communication stability and equal or less overhead than these work.

A topological book embedding of a graph is an embedding in a book that carries the vertices in the spine of the book and the edges in the pages; edges are allowed to cross the spine. Enomoto showed that for any graph G having n vertices, there exists a three-page book embedding of G in which each edge crosses the spine log n times. This paper generalizes the result and shows that for any graph G having n vertices, there exists a d + 1-page book embedding of G in which each edge crosses the spine logd n times.

Recently, the mulitihop wireless network system attracts the interest of many people as a communication network system of the next generation. The multihop wireless network has unique features in which neither base stations nor wired backbone networks are required and a terminal can communicate with the other terminal beyond the transmission range by multihopping. In this network, a communication link between two terminals which can communicate directly is required a channel. Since cochannel interference may occur, we need to assign channels to communication links carefully. In this paper, we describe a channel assignment strategy which takes the degree of cochannel interference into consideration, and we evaluate an effectiveness of this strategy by computer simulations. We show that this strategy is more effective than a strategy which does not take the degree of cochannel interference into consideration. And we also consider a few channel assignment algorithms briefly.

The heterogeneous autonomous decentralized system technology offers a way to integrate different types of context-related autonomous decentralized (sub) systems into a coherent system. The aim of this research is to model and evaluate the communication capacity among the subsystems connected by communication gateways of a heterogeneous autonomous decentralized system. Failures of subsystems and communication gateways in the system are taken into account. We use graphs to represent the topologies of heterogeneous autonomous decentralized systems and use the residual connectedness reliability (RCR) to characterize the communication capacity among its subsystems connected by its gateways. This model enables us to share research results obtained in residual connectedness reliability study in graph theory. Not to our surprise, we learnt soon that computing RCR of general graphs is NP-hard. But to our surprise, there exist no efficient approximation algorithms that can give a good estimation of RCR for an arbitrary graph when both vertices and edges may fail. We proposed in this paper a simulation scheme that gave us good results for small to large graphs but failed for very large graphs. Then we applied a theoretical bounding approach. We obtained expressions for upper and lower bounds of RCR for arbitrary graphs. Both upper and lower bound expressions can be computed in polynomial time. We applied these expressions to several typical graphs and showed that the differences between the upper and lower bounds tend to zero as the sizes of graphs tend to infinite. The contributions of this research are twofold, we find an efficient way to model and evaluate the communication capacity of heterogeneous autonomous decentralized systems; we contribute an efficient algorithm to estimate RCR in general graph theory.

This paper deals with a study of a problem for finding the minimum-cost spanning tree with a response-time bound. The relation of cost and response-time is given as a monotonous decreasing and convex function. Regarding communication bandwidth as cost in an information network, this problem means a minimum-cost tree shaped routing for response-time constrained broadcasting, where any response-time from a root vertex to other vertex is less than a given time bound. This problem is proven to be NP-hard and consists of the minimum-cost assignment to a rooted tree and the minimum-cost tree finding. A nonlinear programming algorithm solves the former problem for the globally optimal solution. For the latter problem, different types of heuristic algorithms evaluate to find a near optimal solution experimentally.

In a multihop network, radio packets are often relayed through inter-mediate stations (repeaters) in order to transfer a radio packet from a source to its destination. We consider a scheduling problem in a multihop network using a graphtheoretical model. Let D=(V,A) be the digraph with a vertex set V and an arc set A. Let f be a labeling of positive integers on the arcs of A. The value of f(u,v) means a frequency band assigned on the link from u to v. We call f antitransitive if f(u,v)f(v,w) for any adjacent arcs (u,v) and (v,w) of D. The minimum antitransitive-labeling problem is the problem of finding a minimum antitransitive-labeling such that the number of integers assigned in an antitransitive labeling is minimum. In this paper, we prove that this problem is NP-hard, and we propose a simple distributed approximation algorithm for it.

Given a plane graph G, we wish to find a drawing of G in the plane such that the vertices of G are represented as grid points, and the edges are represented as straight-line segments between their endpoints without any edge-intersection. Such drawings are called planar straight-line drawings of G. An additional objective is to minimize the area of the rectangular grid in which G is drawn. In this paper first we review known two methods to find such drawings, then explain a hidden relation between them, and finally survey related results.

The use of Internet for various business applications and resource sharing has grown tremendously over the last few years. Internet security has become an important issue for both academic and industrial sectors. Much related network security research has been conducted such as user authentication, data confidentiality, and data integrity. In some applications, a critical document can be divided into pieces and allocated in different locations over the Internet for security access concern. To access such an important document, one must reconstruct the divided pieces from different locations under the given Internet environment. In this paper, a probability model for reconstructing secret sharing and algorithms to perform share assignment are presented. Also, an evaluation algorithm to measure the probability of secret sharing reconstruction is proposed. Illustrative examples and simulation results are provided to demonstrate the applicability of our method.

We model a road network as a directed graph G(V,E) with a source s and a sink t, where each edge e has a positive length l(e) and each vertex v has a distribution function αv with respect to the traffic entering and leaving v. This paper proposes a polynomial time algorithm for evaluating the importance of each edge e E whicn is defined to be the traffic f(e) passing through e in order to assign the required traffic Fst(0) from s to t along only shortest s-t paths in accordance with the distribution function αv at each vertex v.