PLENARY SPEAKER | |
|
Takao Nishizeki (Tohoku University, Japan) |
Title : Inner Rectangular Drawings of Plane Graphs --Application of Graph Drawing to VLSI Layouts (abstract) | |
INVITED SPEAKERS | |
|
Shin-ichi 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 series-parallel graphs with minimum bends (abstract) | |
|
Y. Kusakari (Akita Prefectural University, Japan) |
Title : Methods for Searching Mutual Visible-Intervals 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 Shin-ichi Nakano (with Katsuhisa Yamanaka ) Gunma
University, Japan Abstract
|
|
Methods for Searching Mutual Visible-Intervals on Moving Objects Y.Kusakari (With J.Notoya, Y.Sugimoto, and M.Kasai) Akita Prefectural University, Japan
Abstract Computing visible information, such as visible-surface 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 Visible-Intervals search tree}(MVI-tree) and \textit{Mutual Visible-Intervals search list}(MVI-list). Using these, one can efficiently find an ``mutual visible-surfaces'' on two moving objects from a query time, where the ``mutual visible-surfaces'' is the pair of subregions which are ``visible'' each other. We give algorithms for constructing the MVI-tree and the MVI-list 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 MVI-tree of $\cal{M}$ can be constructed in time $O(N \log N)$ using space $O(N)$ where $N=n_0+n_1$, and the MVI-list of $\cal{M}$ can be constructed in the linear time using linear space. One can find ``mutual visible-intervals'', \textit{i.e.} ``one-dimensional mutual visible-surfaces'', of $\cal{M}$ in time $O(\log N)$ using either MVI-tree or MVI-list. Keyword : Spatio-Temporal Index, Visible-Surface Determination,Mutual Visible-Intervals,Moving Object,MVI-tree,MVI-list. |
|
Orthogonal drawings of series-parallel 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 NP-hard even for trees having exactly one supply vertex and strongly NP-hard for general graphs. In this talk, we focus on the approximability of the problem. We first show that the problem is MAXSNP-hard and hence there is no polynomial-time approximation scheme (PTAS) for general graphs unless ${\rm P}={\rm NP}$. We then present a fully polynomial-time approximation scheme (FPTAS) for trees. The FPTAS can be extended for series-parallel graphs having exactly one supply vertex. |