The representation methods of botanical trees have been presented so far by several researchers in recent years. A great deal of effort has been dedicated mainly to designing a procedural modelling method, especially a growth model of a tree/plant skeleton. However, few previous works have treated the problems of appropriate leaf arrangement and autumn colour evolution of a leaf which are essential to giving natural and seasonal impressions in a close-range view of a tree. In this paper, we will present the simulation methods for these attractive problems based mainly on the estimation of the amount of sunlight and the brightest direction of each part of every leaf.

Abstract Several CG researchers have simulated impressive ocean waves so far. Recently, other researchers have succeeded in simulating waterfalls by employing a mass of particles. However, visual simulation of water currents having complex surfaces, such as mountain streams and turbulent water, still remains a challenging problem thanks to their complicated patterns of behaviour. Effective simulation methods for water currents are expected to have abilities to represent the following remarkable behavioural visual features of water: the appearance of a pool, an obstacle avoidance flow, a fluent flow, a flow into an open space, the collision and the confluence of flows and the occurrence of splashes. In this paper, we present a new type of particle‐based simulation method for complex water currents which is not based on strict fluid dynamics but rather classified into a ‘quasi‐physically‐based’ simulation method constructed on the basis of algorithmic approaches. We first present a simple behavioural model of a ‘water‐particle’. Next, we propose a method for generating CG images of water currents from a set of water‐particles. Finally, we demonstrate the ability of our method by showing several examples of the simulation.

This paper shows that the multicommodity flow problem on a class of planar undirected graphs can be reduced to another famous combinatorial problem, the weighted matching problem. Assume that in a given planar graph G all the sources can be joined to the corresponding sinks without destroying the planarity. Then we show that the feasibility of multicommodity flows can be tested simply by solving, once, the weighted matching problem on a certain graph constructed from G, and that the multicommodity flows of given demands can be found by solving the matching problem $O(n)$ times if G has n vertices. Efficient algorithms are also given for detecting negative and minimum cycles in planar undirected graphs.

This paper deals with the multicommodity flow problems for two classes of planar undirected graphs. The first class C12 consists of graphs in which each source-sink pair is located on one of two specified face boundaries. The second class C01 consists of graphs in which some of the source-sink pairs are located on a specified face boundary and all the other pairs share a common sink located on the boundary. We show that the multicommodity flow problem for a graph in C12 (resp. C01) can be reduced to the shortest path problem for an undirected (resp. a directed) graph obtained from the dual of the original undirected graph.

This paper presents an efficient algorithm for finding multicommodity flows in planar graphs. Suppose that G is an undirected planar graph with all sources and sinks on the boundary of the outer face and that a real-valued demand is given for each source–sink pair. The algorithm decides whether G has multicommodity flows, each from a source to a sink and of a given demand, and actually finds them if G has. It spends $O(kn + n^2 (\log n)^{1/2} )$ time and $O(kn)$ space if G has n vertices and k source–sink pairs.

In this paper, we consider the channel routing problem involving two-terminal nets on rectilinear grids. An efficient algorithm is described which necessarily finds a routing in a given grid whenever it exists. The algorithm is not a heuristic but an exact one, and works for a rather large class of grids, called convex grids, including the grids of rectangular, T-, L-, or X-shape boundaries. Both the running time and required space are linear in the number of vertices of a grid.

Abstract A subset of the vertices of a graph is independent if no two vertices in the set are adjacent. M. O. Albertson proposed an algorithm for finding an independent set that contains more than two‐ninth of the vertices of a planar graph. Refining his algorithm, we give an O (n 2 ) algorithm for the same purpose.

A series-parallel graph can be constructed from a certain graph by recurslvely applying "series" and "parallel" connections The class of such graphs, which Is a well-known model of series-parallel electrical networks, is a subclass of planar graphs It is shown in a umfied manner that there exist hnearume algorithms for many combinatorial problems ff an input graph is restricted to the class of series-parallel graphs.These include 0) the decision problem with respect to a property characterized by a finite number of forbidden graphs, (u) the mlmmum edge (vertex) deletion problem with respect to the same property as above, and (Ul) the generalized matching problem Consequently, the following problems, among others, prove to be hnear-tlme computable for the class of series-parallel graphs.(I) the minimum vertex cover problem, (2) the maximum outerplanar (reduced) subgraph problem, (3) the minimum feedback vertex set problem, (4) the maximum (induced) hne-subgraph problem, (5) the maximum matching problem, and (6) the maximum disjoint triangle problem.

In this paper we consider the maximum independent set problem in which one would like to find a maximum set of independent (i.e., pairwise nonadjacent) vertices in a given graph. The problem is NP-complete, and still remains so even if we restrict ourselves to the class of planar graphs. It has been conjectured that there exist no polynomial-time exact algorithms for any NP-complete problems. We present a polynomial-time approximation algorithm for the maximum independent set problem on planar graphs. For a given planar graph having any number n of vertices, our algorithm finds, in $O(n\log n)$ time, an independent set that is necessarily larger in size than half a maximum independent set. Thus the absolute worst case ratio of our algorithm is greater than $\tfrac{1}{2}$.

Abstract A Hamiltonian walk of a graph is a closed spanning walk of minimum length. In this paper we generalize a Dirac type sufficient condition ensuring the existence of a Hamiltonian cycle to one ensuring the existence of a closed spanning walk of length less than a specified value. Furthermore, we present an O (p2 log p) algorithm for finding such a closed spanning walk in a graph with p vertices satisfying our condition.