Sheung-Hung POON (PhD, HKUST)

Assistant Professor
Department of Computer Science
National Tsing Hua University (NTHU)
Hsin-Chu, Taiwan, R.O.C.



Office: Rm A606, Delta Building

Tel:     +886-3-5731308
Fax:    +886-3-5731201
Email: spoon "at"



Research Interests

Computational Geometry, Computer Graphics, Graph Drawing, Geographic and Information Visualization, Graph Algorithms, and Data Structures.


Current Activities

Steering Committee Member of Asian Association for Algorithm and Computation (AAAC) since  September 2013.

I am the sole representative for the Taiwan region in this Association. Our association holds annual workshop meetings,

which circulate around in Asian countries. We also promote joint research and collaboration activities between Taiwan

and countries in  the whole Asian region. Let’s join our hands, and work together on holding regular research events, and

collaborating on some challenging research projects. Furthermore, we maintain nice relationships with international

organizations around the world.

NTHU Faculty Bible Study Group next noon study meeting on December 26 (Thu), 2013; let's progress together.

In the past five years, there have been Fifteen Master students (including two international students) graduated from

our laboratory. With the caring and guidance of senior PhD student and me, almost all of them graduated with top-

quality theses. Every thesis is the joint work and hard work of the student and the supervisor. You may access their

nice theses through NTHU library. I have advised them in all efforts no matter they were at remote 光復中學 for the

starting five and a half years or they are currently at close 台達館. Most of the Master students graduated from our

laboratory entered big computer, telecommunication or electronic companies in Taiwan. Moreover, there are several

PhD/Master students, who will graduate in half a year; let's work hard together. Currently in our laboratory, with excellent

PhD/Master students and two extremely smart exchange students from Fudan University, we are working hard on several

papers, planned to be submitted to top-tier international conferences and journals:

1)     Domination paper,

2)     Orthogonal drawing paper,

3)     Independent set paper,

4)     Rectilinear drawing paper (with an exchange student, who is going to apply PhD program in university in USA.)

5)     Visibility representation paper, and

6)     Map labeling paper.

Prof. Minming Li from City University of Hong Kong visited me on December 6 (Fri), 2013, and we had a very nice chatting
and research discussion.

To attend the 24th Annual International Symposium on Algorithms and Computation (ISAAC), at University of Hong Kong (HKU),
during December 16-18, 2013, in Hong Kong.

To attend lunch meeting in Hong Kong with AAAC Steering Committee members, Prof. Hee-Kap Ahn, Prof. Siu-Wing Cheng,
Prof. Kazuo Iwama, Prof. Takeshi Tokuyama, and Prof. Guochuan Zhang on December 17, 2013.

To attend a mini-workshop in Taiwan with Prof. Cecilia Bohler, Prof. Franz Aurenhammer, Prof. Rolf Klein, Prof. Chung-Shou Liao,
Prof. D. J. Guan, Prof. Der-Tsai Lee, Prof. Minming Li, Prof. Tien-Ching Lin
, Prof. Martin Nollenburg
during December 19-20, 2013.

Prof. Zhang from Chinese Academy Sciences, Shenzhen Institute and University of Hong Kong visit me during December 23-27,
2013 and we have very nice research discussions.

To visit Hong Kong for research visit and for vacation during January 15 to February 15, 2014.

To visit Prof. Minming Li of City University of Hong Kong to start research collaboration on scheduling topics during January 20-26,
and we have very nice research discussions.

Preparing to submit papers to the 20th International Computing and Combinatorics Conference (COCOON), whose submission
deadline is February 15 (Sat), 2014.

Together with my great PhD student Ching-Hao Liu, we plan to attend the 8th International Workshop on Algorithms and
(WALCOM), at Indian Institute of Technology Madras (IITM), during February 13-15, 2014, in Chennai, India.

We started to go to church near my home (3 minutes by walking) together with President Chuan-Yi Tang (唐傳義校長)
on Sunday, March 2, 2014.

We had a meeting and lunch in Taipei together with Prof. Leonidas Guibas from Stanford University on March 21 (Fri), 2014,
and we had a very nice chatting and discussion.

I attended the Distinguished Lecture of Prof. Christos Papadimitriou from University of California at Berkeley on April 21 (Mon), 2014.
This turns out to be the Best seminar talk I ever attended in my life time, and moreover, he is a very very interesting person to meet.
Originally, at his seminar time, it was my course lecture time; however, since my helpful TAs monitored the midterm examination
of the class for me, I thus luckily got the time to attend this precious seminar. Great thanks to Prof. Hsu's invitation. Maybe in the
future, I will try to attend All invited talks of Prof. Papadimitriou whenever I see such announcements...

Prof. David Mount from University of Maryland, College Park, MD  will visit me at  NTHU  in April, 2014. His  primary  research
area is Computational Geometry. He is a member of the Algorithms and Theory Group at the University of Maryland. He is also one

of the co-authors of the nice Data Structures textbook:
       M. T. Goodrich, R. Tamassia, and D. M. Mount,
       Data Structures and Algorithms in C++
       John Wiley & Sons, New York, 2004.

Prof. David Mount from University of Maryland, College Park, MD will give a talk in our department at 10:10am to 11:10am in April
at Room 106 of Delta Building (new CS building) on the topic:
      Finding Out Where You Are: Simple and Fast on Average

After Prof. Mount's talk, we have lunch with Prof. C.T. King, Prof. Y.S. Chen, Prof. W.K. Hon, Prof. C.S. Liao, and Prof. C.C. Lin together.
We have some chatting and also some interesting discussions about suffix trees, data mining, range searching, and unfolding problems.

I am invited to give a talk in the Algorithm Lab of Prof. R. C. T. Lee (李家同校長) and Prof. C. L. Lu (盧錦隆教授) at 20:10 to 21:10
on May 28 (Wednesday) in Room 550 of EECS Building (old CS Building) on the topic:

Square-Orthogonal Drawing with Few Bends per Edge

Together with my PhD student Ching-Hao Liu, we plan to attend the 30th Annual Symposium on Computational Geometry (SoCG),
at Kyoto University, during June 8-11, 2014, in Kyoto, Japan.

Via the invitation of Prof. Takeshi Tokuyama of Tohoku University, we plan to attend a joint lunch meeting with all session chairs of SoCG
at 13:00 in Kyoto University on June 8 (Sunday), 2014. The number of participants of this meeting is around twenty, and Kyoto-style
lunch boxes will be provided during the meeting.

This year, Prof. Olivier Devillers invited me to chair a session in the prestigious conference, the 30th Annual Symposium on Computational
(SoCG), which will occur at Kyoto University from June 8-11, 2014 in Kyoto, Japan. The session I need to chair is Session 5a from
on June 10 (Tue), 2014.

To visit Prof. Naoki Katoh at Kyoto University for research collaboration on rigidity problems in Computational Geometry during
June 12-18, 2014 just after the SoCG conference, in Kyoto, Japan.

To visit Prof. Kunihiko Sadakane at University of Tokyo for research collaboration on Graph or String Algorithms during June 19-24,
after the SoCG conference, in Tokyo, Japan.

To attend the 8th International Frontiers of Algorithmics Workshop (FAW), during June 28-30, 2014, in Zhangjiajie, China.

To visit Prof. Xujin Chen at University of Chinese Academy of Sciences for research collaboration on packing problems in Graph
during July 4-12, 2014 just after the FAW conference, in Beijing, China.

I am invited by Professor Xiaodong Hu to give a seminar talk at Institute of Applied Mathematics in the Academy of Mathematics and

Systems Science (AMSS) of Chinese Academy of Sciences (CAS) on a topic of non-planar graph drawing on 8 July. Thanks to the

attendees for attendance and for their interesting questions in the Q&A session.

Together with Prof. Chung-Shou Liao, we will visit Prof. Martin Nöllenburg (Leader of Young Investigator Group) at Karlsruher Institut für
Technologie (KIT)
 for research collaboration on Graph Drawing or Map Labeling topics during July 13-26, 2014 in Karlsruhe, Germany.
Here are some currently running Research Projects on Algorithms for Geovisualization of their Young Investigator Group (YIG).

I am invited to give a talk in the research center led by Prof. Dr. Dorothea Wagner of Institute of Theoretical Computer Science at Karlsruhe

Institute of Technology on a topic of orthogonal graph drawing on 25 July. Their group is very strong in graph drawing; after the talk, Ignaz

and Thomas immediately informed me that they recently obtained a simplified proof on a well-known theorem on planar graph drawing.

It is very great to hear that; and then they showed me a few slides to explain the main ideas of the proof in their office. Their proof method

is very brilliant.  :-)

I wrote recommendation letters for student Jiawei Gao. The universities she applied are BrownU, UCaliforniaIrvine, UCaliforniaSanDiego,
ColumbiaU, DukeU, MarylandU, UMichigan, NewYorkU, NorthwesternU, OhioStateU, UPennsylvania, PennsylvaniaStateU, RiceU, RutgersU,
UTexasAustin, and UWisconsin-Madision.
She was accepted to several of the above universities, and was finally admitted to the PhD program
of University of California, San Diego (UCSD). She is currently at the Theory Lab in UCSanDiego. Congratulations to her! She entered the
PhD program directly just after she finished her undergraduate studies. She is a very smart student. When she was an exchange student at
NTHU during her undergraduate studies, we published a great joint theory international conference paper together. Hope her enjoy her
studies in UCSD.

I wrote recommendation letters for student Gabriel Wen. He has been admitted to the Master program of New York University (NYU).
Congratulations to him! He obtained full marks in my "Data Structures" course. In fact, he is not a NTHU student. He comes to NTHU
only to learn several courses. And he learns other courses by self-studying. He is the Most hard-working student I ever met. I am proud
of ever teaching Gabriel. And I always like very much hard-working students. If you have the determination, you must be able to attain
your ultimate target. For some reasons, I always like to support the
weakest. Here I hope Gabriel enjoy his graduate studies in NYU.

My Master student Meng-Huan Liou will attend the 20th International Computing and Combinatorics Conference (COCOON), at Atlanta,

GA, USA during 3-6 August in order to give a presentation on our accepted paper.

Our paper Independent Dominating Set Problem Revisited is recently accepted to the prestigious journal Theoretical Computer Science
in 2014. This is the co-work with my PhD student Ching-Hao Liu; I thus hope that this accepted paper will help him much for the
graduation of his PhD studies in the near future. Let’s work hard together.

1) My PhD student Ching-Hao Liu proposes to graduate on July 30, 2014 ( confirmed with  one-year extension ); let's work hard together.
2) My Master student
Meng-Huan Liou proposes to graduate on July 30, 2014; let's work hard together.

The title of his Master thesis is:  On Edge-Unfolding Special Classes of One-Layer Lattice Polyhedra with Cubic Holes

My Master student Feng-Ren Tsai will graduate soon, say in early September; let's work hard together.

The topic of his Master thesis is:  Orthogonal Drawing and Planarization of Clustered Graphs and Diagrams

To visit again Prof. Kunihiko Sadakane at University of Tokyo for research collaboration on Covering and Star Partition Problems.

To visit Prof. Takeshi Tokuyama and Prof. Matias Korman at University of Tohoku for research collaboration on geometric problems in
Computational Geometry
in Sendai, Japan. We have very great and fruitful joint research discussions together, and it was a very enjoying

and enlightening experience when we had nice research discussions on the interesting topics in  Computational Geometry.

Our paper Optimally Bracing Grid Frameworks with Holes is accepted to the 8th International Conference on Combinatorial Optimization
and Applications
, 2014.

I am invited by Professor Takahashi and Professor Wu to give a seminar talk in Department of Complexity Science and Engineering at

University of Tokyo on a topic of Edge-Unfolding Lattice Polyhedra in September, 2014. It’s my great honor to have this precious chance.

Prof. Shigeo Takahashi’s research laboratory has conducted many interesting research on Information Visualization, Scientific Visualization,

and Visual Analytics topics. We had very interesting and fruitful research discusions on Metro map layout visualization, 3D surface unfolding

or surgery, and Dynamic map visualization topics. We have submitted some of our completed work to top-tier Information Visualization


Our paper on 環状経路を中心とする地下鉄路線図レイアウト設計 is to appear in CSIS Day, 2014, in Japan.

Our paper On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs, and chordal bipartite graphs

is accepted to  Journal of Discrete Algorithms.

Prof. Kai-Min Chung from Academia Sinica gave a talk in our department at 1:30pm to 3:00pm in December this year in EECS Building (old CS
building) on the topic:
      Statistically-secure Oblivious RAMs with Improved Efficiency

Before Prof. Chung's talk, we had lunch with Prof. J.J. Chen, Prof. W.K. Hon, Prof. C.S. Liao, and Prof. Y. Yin together. We have some chatting

and also some interesting research discussions.

Recently, I wrote recommendation letters for student Tianhao Wang. He is now applying for PhD programs in several universities in U.S.A.

He is the Smartest student I ever taught. Most of the grades of his courses are ranked No. 1 in the whole class. Moreover, he has very strong

analytical ability on solving specific problems. Wish him every luck in being admitted to some of those universities he likes. The eight universities

he applied are UCBerkeley, ColumbiaU, JohnsHopkinsU, MarylandU, PurdueU, RutgersU, UTexasAustin, and UWisconsin-Madision. Recently,

he obtained several offers from some of these universities, and he finally decided to go to Purdue University to pursue his PhD studies, say in coming

September. I thus wish that he will enjoy his studies in PurdueU.

Our paper On Edge-Unfolding One-Layer Lattice Polyhedra with Cubic Holes is invited for submission to the prestigious special issue journal
of COCOON conference, which is
Algorithmica. It’s our honor to obtain this invitation in the new year. [ accomplished in  2015 ]

Our paper Optimally Bracing Grid Frameworks with Holes is invited for submission to the prestigious special issue journal of COCOA conference,
which is
Theoretical Computer Science. It’s our honor to obtain this invitation in the new year. [ accomplished in  2015 ]

Our paper, Algorithm for Finding All k-edge-connected Components, is submitted to a journal in the year of  2015.
[ This is the collaborated work with University of Hong Kong (HKU). ]

Our paper, Scheduling Tasks to Minimize Active Time on a Processor with Unlimited Capacity, is submitted to the 12th Workshop on Models and
Algorithms for Planning and Scheduling Problems

[ This is the collaborated work with Prof. Li from City University of Hong Kong (CityUHK). ]

Our paper On Maxmin Active Range Problem for Weighted Consistent Dynamic Map Labeling is accepted to the 11th International Conference
on Advanced
Geographic Information Systems, and Services
GeoProcessing),  2015.

Our paper, my student Jin-Yong Lin’s paper with title Algorithms and Hardness for Signed Domination, is accepted to the 12th Annual Conference
on Theory and Applications of Models of Computation

I am invited as the session chair of the combinatorial algorithms session in the 9th International Workshop on Algorithms and Computation
2015. This year, the conference received 88 submissions, and among them, 29 papers are accepted to be presented in the

I am invited to act as the Program Committee member of the 8th Annual Meeting of Asian Association for Algorithms and Computation (AAAC),  2015.
The meeting will occur during
May 9-10, 2015 at Miyajima, Hiroshima, Japan.

My former student, Mr. Mustapha Ceesay, has made applications of PhD programs to the College of Management in both NCTU and NTHU.

I help him to write recommendation letters. I thus wish him good luck in obtaining the admissions from the corresponding universities.

Our journal paper, the joint work with my student Ching-Hao Liu and other authors, with title On Maximum Independent Set of Categorical Product
and Ultimate Categorical Ratios of Graphs
, is accepted to the prestigious journal Theoretical Computer Science in 2015.

I am invited to give a talk / lecture at the International Spring School on Algorithms and Applications (ISSAA),  2015.

I am invited to act as the Program Committee member of the 10th International Workshop on Algorithms and Computation (WALCOM),  2016.


Geometric Computing,

       Graph Drawing, and


       (3G Lab)            Laboratory

Recruitment in Our Laboratory

We are looking for excellent PhD and master students graduating from NTHU or from other universities to help develop our laboratory.

Our laboratory targets at training students to submit papers to top international conferences and journals. Our research focuses on very

interesting geometric problems arising in the fields of geographic information system (GIS), bioinformatics, computer graphics, graph

drawing, and wireless networks. We investigate the complexity of the proposed optimization problems, and we further design efficient

optimal or approximation algorithms in theory or in practice. On one hand, students are invited to get involved in the ongoing projects

in our laboratory; and on the other hand, they are also highly encouraged to propose and investigate, themselves, brand-new problems

they are interested in. Members in our laboratory would have opportunities to attend top conferences and to visit foreign laboratories

in the related research field.

We are currently seriously recruiting many new PhD and Master students
to start at Fall Semester this year. Please contact PI

in our laboratory immediately. We expect our laboratory to grow rapidly in the near future. Students who would like to ask me

to be their potential supervisor, can drop by my office any time, or send me an email (or make me a phone call) beforehand to make

sure I am in my office. When you come, it would be good if you can bring along your transcript. Thanks you very much for your kind


Auxiliary Information

Foreign Languages.  (Learn as if you were to live forever.  --  M. Gandhi)
Nowadays, there are many online language learning materials. It seems to be a wastage if we do not make use of them. One of my

PhD students can listen to and understand Japanese very well. Apart from Japanese, other language also looks interesting to me,

such as German or other Asian and European languages.

On Everyday: (Let’s do more exercise.)
In order to reduce a few kilograms away from my body, I try to walk, hike, run or bike for at least thirty minutes on a daily basis.

I have NEVER ever used an Apple product, such as iPhone, iPad, or MacBook, anywhere. They should be great products.

But they are just not compatible to me up to this moment. Sorry to Apple …

John 15:12:

My command is this: Love each other as I have loved you.

1 Corinthians 13:13:

And now these three remain: faith, hope and love. But the greatest of these is love.

Psalm 33:5:

The Lord loves righteousness and justice; the earth is full of his unfailing love.

Hebrews 11:1:

Now faith is confidence in what we hope for and assurance about what we do not see.

James 2:22:

You see that his faith and his actions were working together, and his faith was made complete by what he did.

2 Corinthians 13:11:

Finally, brothers and sisters, rejoice! Strive for full restoration, encourage one another, be of one mind, live in peace. And the God of

love and peace will be with you.

At Hsinchu:

Holy Spirit Church

At Brunei:

St. Geoge Church

At Christmas Eve: (平安夜,報平安)
Optimism, when applied to your life, develops strength and peace within you.   --   Norman Vincent Peale

To my students.  (Wonder is the beginning of wisdom.  --  Socrates)
It has been my usual practice that you’re very welcome to drop by my office to have some chatting or discussions with me even

though you do not make appointment with me beforehand.

Forever Danny.  (my favorite singer during high school time)



At Christmas time: (I was born the day after Christmas day.)
Come to visit my home town, Hong Kong, during this wonderful festival, and enjoy the Christmas lights there. It is ranked second

in the top-10 winter destinations three years ago.

St. Joseph's Anglo-Chinese School (SJACS).  ( my former secondary school )
School Motto:
In Latin: "
AD Astra, Caritas"
In English: "To the stars, Benevolence"
In Chinese:

Our Founder – Reverend Brother Paul Sun:
Born in Reihe, now Inner Mongolia, Brother Paul Sun devoted his life to Christ and education at the age of 19 as a brother disciple of the

Society of the Most Sacred Heart of Jesus. After completing his school education, he moved to Beijing to study at the Catholic University

of Peking (北平輔仁大學) and later in Japan under the sponsorship of the Society.  In 1940 he was elected the first Chinese superior general

of the Society. In 1949 he left China and founded a school in Indonesia. He came to Hong Kong in 1952 and taught and acted as a warden

at La Salle College. In 1958, with the support of the De La Salle Brothers, the Marist Brothers and some other friends, he succeeded in

establishing St Joseph’s Anglo-Chinese School, initially with 455 boys in humble premises converted from a villa. For a few years the school

had to operate in three sessions each day, until a new wing was added in 1962. With Government support, a stand-alone school building

for the secondary section was completed in 1968.


Brother Paul placed the school under the special patronage of Saint Joseph drawing hope from his model of parental care and mirroring

the love of the Holy Family.  In 1971 he was honoured as an affiliate of the De La Salle Brothers. He passed away on March 13, 1986.


True to the spirit of Christian love, Brother Paul’s vision was to offer education to all who aspired to learn including many who might

otherwise have been deprived of the opportunity to develop their potential. This philosophy is well-enshrined in the School’s motto of

“Ad Astra” and “Benevolence”.




Last Updated: 22 May 2013