Invited Speakers

 
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 drawing of a plane graph is called an inner rectangular drawing if every edge is drawn as a horizontal or vertical line segment so that every inner face is a rectangle.  An inner rectangular drawing has some applications to VLSI layouts. In this talk we show that a plane graph $G$ has an inner rectangular drawing $D$ if and only if a new bipartite graph constructed from $G$ has a perfect matching. We also show that $D$ can be found in time $O(n^{1.5}/\log n)$ if $G$ has $n$ vertices and a sketch of the outer face is prescribed, that is, all the convex outer vertices and concave ones are prescribed. This is a joint work with K. Miura and H. Haga.

[back to top]


A Compact Encoding of some graphs

Shin-ichi Nakano (with Katsuhisa Yamanaka )

Gunma University, Japan
 

Abstract


A rectangular drawing is a plane drawing in which every face is a rectangle. In our research, we give a simple encoding scheme for rectangular drawings. The encoding scheme needs 5m/3 + o(n) bits for each n-vertex rectangular drawing R, where m is the number of edges of R, and supports a rich set of queries, including adjacency and degree queries, in constant time.

[back to top]


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.

 [back to top]


Orthogonal drawings of series-parallel graphs with minimum bends 

Xiao Zhou

Tohoku University, Japan

 

Abstract

[back to top]


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.

[back to top]