Computational Geometry, Graphs and Applications: International Conference,CGGA 2010, Dalian, China, November 3-6, 2010, Revised, Selected Papers (Lecture Notes in Computer Science, 7033)

Annotation This book constitutes the thoroughly refereed post-conference proceedings of the China-Japan Joint Conference on Computational Geometry, Graphs and Applications, CGGA 2010, held in Dalian, China, in November 2010. The 23 revised full papers presented were carefully selected during two rounds of reviewing and improvement from numerous submissions. All aspects of computational and discrete geometry, graph theory, graph algorithms, and their applications are covered Title Preface Organization Table of Contents Determination of All Tessellation Polyhedra with Regular Polygonal Faces Introduction Regular Faced Tessellation Polyhedra Another Necessary Condition for Regular Faced Polyhedra to Have the Tessellation Property Main Theorem References Regular Graphs with Maximum Forest Number Introduction Connected Subclasses The Main Results $r+1\le n\le 2r-1$ $n\ge 2r$ References Semi Voronoi Diagrams Introduction Some Preliminary Results When the Visible Angle Is 180 When the Visible Angle Is Not 180 Area Not Controlled by Any Member in P Partition of the Plane by Two Sets Future Studies References Making Polygons by Simple Folds and One Straight Cut Introduction Definitions Passages Algorithm High-Level Algorithm Algorithmic Details Correctness Passage Invariant Shrinking Excess Paper Feasible Folds Are Safe Approaching the Convex Hull (Step 1) Approaching Limit Endpoints (Step 3) Convex Polygons Conclusion References Common Unfoldings of Polyominoes and Polycubes Introduction Unfolding Path-Like Polyominoes Unfolding Polycubes Path-Like Planar Polycubes Tree-Like Planar Polycubes Pentacubes References Affine Equivalent Classes of Parallelohedra Introduction, Basic Notions The Uniqueness Theorem References Fr\'{e} chet-Distance on Road Networks Introduction Preliminaries Computing the Fréchet-Distance Based on Network Distance Decision Problem Optimization Problem Variants of the Fréchet Distance Based on Network Distance The weak Fréchet-Distance Based on Network Distance The Discrete and Weak Discrete Frechét-Distance Based on Network Distance Conclusions References Acute Triangulations of the Cuboctahedral Surface Introduction Non-obtuse Triangulations Acute Triangulations No Acute Triangulation with Fewer Triangles References Edge Clique Partition of K4-Free and Planar Graphs Introduction Preliminaries K4-Free Graphs Planar Graphs Planar K4-Free Graphs Conclusions References Generation of Polyiamonds for p6 Tiling by the Reverse Search Introduction Preliminaries Generation Algorithms for p6 Tiling Family Trees Generating Polyiamonds Counting the Number of Polyiamonds Experimental Results Conclusions References Continuous Flattening of Platonic Polyhedra Introduction Lemma and Propositions Theorems and Proofs Further Research References Minimal Embedding of Hypercubic Graphs on Surface Introduction and Definition Lower Bound of (G) Upper Bound of (Qn) Minimal Embedding of Qn Conclusions References A Morphology Method for Determining the Number of Clusters Present in Spectral Co-clustering Documents and Words Introduction Typical Spectral Co-clustering Documents and Words Our Method for Determining the Number of Clusters Present in Spectral Co-clustering Documents and Words Generating a VAT Image Filtering the VAT Image Determination of Cluster Number Experimental Results and Comparisons Results on Different Methods for Automatically Determining the Number of Clusters Results for Modified Spectral Co-clustering Documents and Words Method Conclusion References A Property about the Convex Lattice Set in ZZ$^2$ Introduction Proof of Main Result References On the Diameter of a Circle to Hold a Cube Introduction A Few Lemmas The Cube Case Outline of the Octahedron Case References An A* Algorithm Framework for the point-to-point Time-Dependent Shortest Path Problem Introduction Time-Dependent A* Algorithm Framework for TDSPP Time-Dependent ALT Algorithm for TDSPP Experimental Results Conclusion References Monotonic Polygons and Paths in Weighted Point Sets Introduction Monotonic Polygons in wp-sets wp-sets in Convex Position wp-sets in General Position Counting Monotonic Convex k-gons in PCn Monotonic Empty Quadrilaterals in PPn Lower Bound Upper Bound Monotonic Paths in wp-sets in Convex Position References Simple Characterization of LR-visibility Polygons Introduction Preliminary Characterizing LR-visibility Polygons Recognizing LR-visibility Polygons Shortest Path Trees in an LR-visibility Polygon Computing All Non-redundant Backward Components The Algorithm and Its Analysis References A 7/6-Approximation Algorithm for the Max-Min Connected Bipartition Problem on Grid Graphs Introduction Preliminaries Non-separating Connectors An Approximation Algorithm for GBCP2 Concluding Remarks References Local Modification of Skin Surface Mesh: Towards Free-Form Skin Surface Deformation Introduction Background Delaunay and Voronoi Complexes Skin Skin Deformation and Local Modification Dynamic Skin Triangulation Local Modification of Skin Surface Updates on Delaunay and Voronoi Complexes Mixed Cells Deformation Surface Points Movements Maintaining the Mesh by Scheduling Algorithm Scheduling Edge Update Scheduling Triangle Update Handling Topology Changes Scheduling of Topology Preserving Operations Hyperboloid Warping Experiment Results and Conclusion References A Kind of Triangle Covering and Packing Problem Introduction Covering an Equilateral Triangle with Equilateral Triangles Packing an Equilateral Triangle by Equilateral Triangles References Consecutive Edge-Colorings of Generalized $\theta$ -Graphs Introduction and Preliminary Upper Bound of S($\theta$ m) CEC of m with Possible Spans Concluding Remarks References Author Index Edited By Jin Akiyama, Jiang Bo, Mikio Kano, Xuehou Tan.