PLENARY SPEAKER  

Takao Nishizeki (Tohoku University, Japan) 
Title : Inner Rectangular Drawings of Plane Graphs Application of Graph Drawing to VLSI Layouts (abstract)  
INVITED SPEAKERS  

Shinichi Nakano (Gunma University, Japan) 
Title : A Compact Encoding of some graphs (abstract )  

Subhas Chandra Nandi (Indian Statistical Institute, Kolkata, India) 
Title :  

Xiao Zhou (Tohoku University, Japan) 
Title : Orthogonal drawings of seriesparallel graphs with minimum bends (abstract)  

Y. Kusakari (Akita Prefectural University, Japan) 
Title : Methods for Searching Mutual VisibleIntervals on Moving Objects (abstract)  

Takehiro Ito (Tohoku University, Japan) 
Title : Partitioning Graphs of Supply and Demand (abstract)  
Inner Rectangular Drawings of Plane Graphs Application of Graph Drawing to VLSI Layouts Takao Nishizeki Tohoku University, Japan
Abstract


A Compact Encoding of some graphs Shinichi Nakano (with Katsuhisa Yamanaka ) Gunma
University, Japan Abstract


Methods for Searching Mutual VisibleIntervals on Moving Objects Y.Kusakari (With J.Notoya, Y.Sugimoto, and M.Kasai) Akita Prefectural University, Japan
Abstract Computing visible information, such as visiblesurface determination, is a significant problem and has been mainly studied in the fields of computational geometry and computer graphics. Furthermore,recently, one might be attracted to the problems for dealing with the continuously moving objects in a geometrical space. In this paper, we propose two indexing methods, called \textit{Mutual VisibleIntervals search tree}(MVItree) and \textit{Mutual VisibleIntervals search list}(MVIlist). Using these, one can efficiently find an ``mutual visiblesurfaces'' on two moving objects from a query time, where the ``mutual visiblesurfaces'' is the pair of subregions which are ``visible'' each other. We give algorithms for constructing the MVItree and the MVIlist from the set $\cal{M}$ of two convex polygons $M_0$ with $n_0$ vertices and $M_1$ with $n_1$ vertices, in the case where each convex polygon moves by uniform motion. The MVItree of $\cal{M}$ can be constructed in time $O(N \log N)$ using space $O(N)$ where $N=n_0+n_1$, and the MVIlist of $\cal{M}$ can be constructed in the linear time using linear space. One can find ``mutual visibleintervals'', \textit{i.e.} ``onedimensional mutual visiblesurfaces'', of $\cal{M}$ in time $O(\log N)$ using either MVItree or MVIlist. Keyword : SpatioTemporal Index, VisibleSurface Determination,Mutual VisibleIntervals,Moving Object,MVItree,MVIlist. 

Orthogonal drawings of seriesparallel graphs with minimum bends Xiao Zhou Tohoku University, Japan
Abstract 

Partitioning Graphs of Supply and Demand Takehiro Ito Tohoku University, Japan
Abstract Suppose that each vertex of a graph $G$ is either a supply vertex or a demand vertex and is assigned a positive real number, called the supply or the demand. Each demand vertex can receive ``power'' from at most one supply vertex through edges in $G$. One thus wishes to partition $G$ into connected components so that each component $C$ either has no supply vertex or has exactly one supply vertex whose supply is at least the sum of demands in $C$, and wishes to maximize the fulfillment, that is, the sum of demands in all components with supply vertices. This maximization problem is known to be NPhard even for trees having exactly one supply vertex and strongly NPhard for general graphs. In this talk, we focus on the approximability of the problem. We first show that the problem is MAXSNPhard and hence there is no polynomialtime approximation scheme (PTAS) for general graphs unless ${\rm P}={\rm NP}$. We then present a fully polynomialtime approximation scheme (FPTAS) for trees. The FPTAS can be extended for seriesparallel graphs having exactly one supply vertex. 