Registration Registration Registration
Geometry I
Algorithms I
Approximation Algorithms
Tea Break Tea Break Tea Break
Keynote 1:
Etsuji Tomita
Keynote 3:
Francis Chin
Algorithms II
Lunch Break Lunch Break


1. Daxi Tea Factory
2. Neiwan Township
Combinatorial Optimization Computational
Geometry II
Tea Break Tea Break
Keynote 2:
Peter Eades
Space-efficient Algorithms
Tea Break Tea Break
Computational Complexity
& Reception

March 28 (Tuesday)

18:30-21:00    Reception (150min)
Location: Conference Room 1 on the 1st floor, Microelectronics and Information System Research Center, National Chiao Tung University.

March 29 (Wednesday)

Location: Conference Room 4 on the 1st floor, Microelectronics and Information System Research Center, National Chiao Tung University.

9:00-10:40    Computational Geometry I (100min)
Naoki Katoh (Kwansei Gakuin University, Japan)

  • Efficient Enumeration of Flat-Foldable Single Vertex Crease Patterns
     Koji Ouchi and Ryuhei Uehara
  • Dynamic Sum-Radii Clustering
     Nicolas Blanchard and Nicolas Schabanel
  • How to Extend Visibility Polygons by Mirrors to Cover Invisible Segments
     Arash Vaezi and Mohammad Ghodsi
  • On Guarding Orthogonal Polygons with Sliding Cameras
     Therese Biedl, Timothy M. Chan, Stephanie Lee, Saeed Mehrabi, Fabrizio Montecchiani and Hamideh Vosoughpour
  • Bundling Two Simple Polygons to Minimize Their Convex Hull
     Jongmin Choi, Dongwoo Park and Hee-Kap Ahn

11:00-12:00    Keynote 1 (60min)
Md Saidur Rahman (Bangladesh University of Engineering and Technology, Bangladesh)

  • Efficient Algorithms for Finding Maximum and Maximal Cliques and Their Applications
     Etsuji Tomita (The University of Electro-Communications, Japan)

13:10-14:30    Combinatorial Optimization (80min)
Bertrand M.T. Lin (National Chiao Tung University, Taiwan)

  • Tangle and maximal ideal
     Koichi Yamazaki
  • A width parameter useful for chordal and co-comparability graphs
     Dong Yeap Kang, O-Joung Kwon, Torstein Strømme and Jan Arne Telle
  • Byzantine gathering in networks with authenticated whiteboards
     Masashi Tsuchida, Fukuhito Ooshita and Michiko Inoue
  • Generating All Patterns of Graph Partitions within a Disparity Bound
     Jun Kawahara, Takashi Horiyama, Keisuke Hotta and Shin-Ichi Minato

14:50-15:50    Keynote 2 (60min)
Sheung-Hung Poon (University of Technology Brunei, Brunei Darulssalam)

  • A Few Steps Beyond Planarity
      Peter Eades (University of Sydney, Australia)

16:10-17:10    Graph Drawing (60min)
Peter Eades (University of Sydney, Australia)

  • An Experimental Study on the Ply Number of Straight-line Drawings
     Felice De Luca, Emilio Di Giacomo, Walter Didimo, Stephen Kobourov and Giuseppe Liotta
  • Complexity Measures for Mosaic Drawings
     Quirijn Bouts, Bettina Speckmann and Kevin Verbeek
  • Fast Optimal Labelings for Rotating Maps
     Rafael Cano, Cid de Souza and Pedro de Rezende

March 30 (Thursday)

9:00-10:40    Graph Algorithms I (100min)
Ryuhei Uehara (Japan Advanced Institute of Science and Technology, Japan)

  • Recognizing Simple-Triangle Graphs by Restricted 2-Chain Subgraph Cover
     Asahi Takaoka
  • Tree-Deletion Pruning in Label-Correcting Algorithms for the Multiobjective Shortest Path Problem
     Fritz B¨okler and Petra Mutzel
  • Minimum Weight Connectivity Augmentation for Planar Straight-Line Graphs
     Hugo Akitaya, R. Inkulu, Torrie Nichols, Diane Souvaine, Csaba Toth and Charles Winston
  • A fast deterministic detection of small pattern graphs in graphs without large cliques
     Miroslaw Kowaluk and Andrzej Lingas
  • Approximation algorithm for the distance-3 independent set problem on cubic graphs
     Hiroshi Eto, Takehiro Ito, Zhilong Liu and Eiji Miyano

11:00-12:00    Keynote 3 (60min)
Hsu-Chun Yen (National Taiwan University, Taiwan)

  • Why Genome Assembly is Difficult?
      Francis Chin (Hang Seng Management College and University of Hong Kong, Hong Kong)

13:10-14:30    Computational Geometry II (80min)
Takeshi Tokuyama (Tohoku University, Japan)

  • Online Inserting Points Uniformly on the Sphere
     Chun Chen, Francis Lau, Sheung-Hung Poon, Yong Zhang and Rong Zhou
  • Computing the Center Region and Its Variants
     Eunjin Oh and Hee-Kap Ahn
  • Fault-Tolerant Spanners in Networks with Symmetric Directional Antennas
     Mohammad Ali Abam, Fatemeh Baharifard, Mohammad Sadegh Borouny and Hamid Zarrabi-Zadeh
  • Gathering Asynchronous Robots in the Presence of Obstacles
     Subhash Bhagat and Krishnendu Mukhopadhyaya

14:50-15:50    Space-efficient Algorithms (60min)
Krishnendu Mukhopadhyaya (Indian Statistical Institute, India)

  • A Space-Efficient Algorithm for the Dynamic DFS Problem in Undirected Graphs
     Kengo Nakamura and Kunihiko Sadakane
  • Time-Space Trade-off for Finding the k-Visibility Region of a Point in a Polygon
     Yeganeh Bahoo, Bahareh Banyassady, Prosenjit Bose, Stephane Durocher and Wolfgang Mulzer
  • Space-Efficient and Output-Sensitive Implementations of Greedy Algorithms on Intervals
     Toshiki Saitoh and David Kirkpatrick

16:10-17:10    Computational Complexity (60min)
Kunihiko Sadakane (The University of Tokyo, Japan)

  • Algorithms for Automatic Ranking of Participants and Tasks in an Anonymized Contest
     Yang Jiao, R. Ravi and Wolfgang Gatterbauer
  • The Complexity of (List) Edge-Coloring Reconfiguration Problem
     Hiroki Osawa, Akira Suzuki, Takehiro Ito and Xiao Zhou
  • An Upper Bound for Resolution Size: Characterization of Tractable SAT Instances
     Kensuke Imanishi

17:30-20:30    Banquet
Location: Amazing Hall, Hsinchu
Address: No 105, Sec 2, Gongdao 5th Rd., Hsinchu City 30070, Taiwan

March 31 (Friday)

9:00-10:40    Approximation Algorithms (100min)
Lusheng Wang (City University of Hong Kong, Hong Kong)

  • Finding Triangles for Maximum Planar Subgraphs
     Parinya Chalermsook and Andreas Schmid
  • An Approximation Algorithm for Maximum Internal Spanning Tree
     Zhi-Zhong Chen, Youta Harada, Fei Guo and Lusheng Wang
  • Approximation algorithm for cycle-star hub network design problems and cycle-metric labeling problem
     Yuko Kuroki and Tomomi Matsui
  • Improved approximation for two dimensional strip packing with polynomial bounded width
     Klaus Jansen and Malin Rau
  • An FPTAS for Computing the Distribution Function of the Longest Path Length in DAGs with Uniformly Distributed Edge Lengths
     Ei Ando

11:00-12:00    Graph Algorithms II (60min)
Eiji Miyano (Kyushu Institute of Technology, Japan)

  • Sequentially Swapping Colored Tokens on Graphs
     Katsuhisa Yamanaka, Erik D. Demaine, Takashi Horiyama, Akitoshi Kawamura, Shin-Ichi Nakano, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara and Takeaki Uno
  • The Time Complexity of the Token Swapping Problem and Its Parallel Variants
     Jun Kawahara, Toshiki Saitoh and Ryo Yoshinaka
  • Sliding tokens on block graphs
     Duc Hoang, Eli Fox-Epstein and Ryuhei Uehara

12:00-18:00    Lunch & Excursion

12:15-13:25: Drive to Daxi Tea Factory
13:25-14:25: Tour in Daxi Tea Factory

Built in 1926, and was formerly named the "Jiaoban Mountain Factory." The architecture is a fusion of Taiwanese, Japanese, and British styles. At that time, Taiwanese tea was prosperous. It was a time when tea was regarded as "black gold."

14:30-15:45: Drive to Neiwan
15:45-16:45: Free Activity in Neiwan Township

Neiwan was the township that gathers important materials such as lime stone, coal and wood.It is one of the most important tourist attractions in the Hsinchu area. Featuring its special products, such as ginger lily-flavored glutinous rice, further add to hospitality and friendliness on the Old Street.

16:50-18:00: Drive to NCTU