平面グラフの格子短形描画
スポンサーリンク
概要
- 論文の詳細を見る
In this paper we consider the rectangular drawing of a plane graph, where each edge of the graph is drawn as a horizontal or vertical line segment with no bend and each face of the graph is drawn as a rectangle (see Fig.1).Thomassen obtained a necessary and sufficient condition for a plane graph to have a rectangular drawing. A straightforward implementation of his method requires Ο(n^3)time. We give a new constructive proof of Thomassen's characterization, and give a simple algorithm to find a rectangular grid drawing of a plane graph in linear time. We also give upper bounds on the sizes of rectangular grid drawings: W×H ≤ n^2/(16)and W+H ≤ n/2where W is the width and H is the height of the required grid. The bounds are tight and best possible. [figure]
- 社団法人電子情報通信学会の論文
- 1996-03-11
著者
-
Nishizeki Takao
Graduate School Of Information Sciences Tohoku University
-
Nishizeki Takao
Graduate School Of Information Sciences
-
Rahman Md.Saidur
Graduate School of Information Sciences
-
Nakano Shin-ichi
Graduate School of Information Sciences
関連論文
- List Edge-Colorings of Series-Parallel Graphs
- Linear Algorithm for Finding List Edge-Colorings of Series-Parallel Graphs (Special Issue on Selected Papers from LA Symposium)
- Quantum Card Dealing
- Necessary and Sufficient Numbers of Cards for Sharing Secret Keys on Hierarchical Groups(Special Issue on Selected Papers from LA Symposium)
- Sufficient Condition and Algorithm for List Total Colorings of Series-Parallel Graphs(Discrete Mathematics and Its Applications)
- Algorithms for Drawing Plane Graphs(Foundations of Computer Science)
- 平面グラフの格子短形描画
- On the One-Way Algebraic Homomorphism (Special Section on Cryprography and Information Security)
- Cost Total Colorings of Trees(Foundations of Computer Science)
- LA-10 A Linear Algorithm for Rectangular Drawings of Planar Graphs
- LA-9 Rectangle-of-Influence Drawings of Four-Connected Plane Graphs
- Edge-Coloring Problems for Graphs
- Mining Communities on the Web Using a Max-Flow and a Site-Oriented Framework(Data Mining)
- Partitioning a Multi-Weighted Graph to Connected Subgraphs of Almost Uniform Size(Graph Algorithms,Foundations of Computer Science)
- Algorithms for Multicolorings of Partial ★-Trees (Special Issue on Selected Papers from LA Symposium)
- Convex Drawings of Internally Triconnected Plane Graphs on O(n^2) Grids
- Best Security Index for Digital Fingerprinting(Information Hiding, Cryptography and Information Security)
- Efficient Compression of Web Graphs
- Generalized Edge-Rankings of Trees
- One-Way Functions over Finite Near-Rings
- An Improved Algorithm for the Nearly Equitable Edge-Coloring Problem