Dr. Stephen Wismath
Professor Emeritus
Department of Mathematics and Computer Science,
University of Lethbridge,
4401 University Dr.,
Lethbridge, Alberta,
Canada
T1K-3M4
e-mail:
My
Curriculum Vitae in pdf form.
Biography:
Dr. Wismath received his Ph.D. in Computer Science from U.B.C. in 1989.
He obtained his B.Sc. (Hons., Mathematics) with a minor in Computing
Science in 1975 and
an M.Sc. (Computing Science) in 1980 from Queen's University.
He is a Professor Emeritus and taught primarily computer science courses
at the University of Lethbridge since 1983.
He took a turn as Chair of the department, finishing June 30, 2009.
Hobbies:
I've been a runner for over 50 years and have completed 7 marathons
and numerous shorter races (mostly 10 mile and 1/2 marathon distances recently).
I also play go
regularly and avidly.
Teaching:
No further teaching duties! Ever.
Here are some
projects
generated by my students in the Computer Graphics
course recently.
Research Interests:
Currently, the main focus of my research is examining the
nature and structure of visibility among objects in the plane and
determining efficient and practical algorithms for such problems.
More recently, graph drawing in three dimensions has been of
primary interest.
In general, my research
can be categorized as:
Analysis of Algorithms, Computational Geometry, Graph Drawing,
Visibility Graphs.
I gratefully acknowledge NSERC for their support of my research.
Conferences
I was invited to give a talk at
Graph Theory with Altitude in May 2005.
I was invited to give a course on
3-Dimensional Straight-Line Graph Drawing
at the
Journees de Geometrie Algorithmique 2002
held in Obernai, France,
Oct 14-18, 2002.
I hosted the
14th Canadian Conference on Computational Geometry
here in Lethbridge August 12-14, 2002.
Together with Hazel Everett (LORIA, U. Nancy, France), I was editor for
a special issue devoted to this conference in the journal
Computational Geometry: Theory and Applications
Volume 28, Issue 1 [SPECIAL ISSUE], May-2004
Program Committees:
Recently:
Graduate Students:
LillAnne Jackson -- graduated in 1996.
Thesis: Polygon Reconstruction from Visibility Information.
Elspeth Nickle -- graduated in Fall 2005
Thesis:
Classes of Arrangement Graphs in 3D.
Sebastian Hanlon -- graduated in Spring 2006.
Thesis: Visualizing 3D Graph Drawings.
Andrew Butcher -- cosupervised with Matt Tata (Neuroscience)
-- graduated Spring 2012
Thesis: Free Field Auditory Localization and Perception.
Joel Bennett -- cosupervised with Kevin Grant -- graduated Fall 2014.
Thesis: Voxel Octree intersection based 3D scanning.
Farshad Barahimi
-- graduated Summer 2015
Thesis: Web-based drawing software for graphs in 3D and two layout algorithms.
Summer research (undergraduate) students:
In the last several years, I have hired the following students to
work on research projects:
Helen Pinto, Michael Closson, Breanne Dyck, Shane Gartshore, Ray Dufresne,
John Johansen, Jill Joevenazzo, Jon Wilsdon, Kim Hansen, Sebastian Hanlon,
Carrie Wang, Ethan Kim, Garret Johnson, Amy Smith, Ian Stewart, Fei Wang, Lezar DeGuzman.
Research Projects and Software:
3D Graph Visualization with the Oculus Rift with Farshad Barahimi
is a poster accepted and presented at Graph Drawing 14.
Animation of an Algorithm for Drawing Graphs in 3D with Lezar DeGuzman
is an animation accepted and presented at the Symposium on Computational Geometry, 2014 in Kyoto, Japan
It comes in both a 2D and a 3D version.
3D Printed Graphs with GLuskap
(with Joel Bennett)
was a poster accepted and presented at Graph Drawing 13.
The GLUSKAP
(version 3.0) package for
3D graph drawing is now available.
An earlier version was presented as a
poster at
Graph Drawing 2003.
Using this software we entered the
graph drawing contest
associated with the
GD03 conference and tied for 2nd place. Our entry includes 2 animations and a
stereogram poster.
An animation (by Carrie Wang with some post processing by Kim Hansen) is on
upward drawings of trees in 3D
and was entered in the Graph Drawing 2005 freestyle contest.
We have several other projects on the go. See this
web site for various projects.
An
animation on drawing planar graphs
produced by my student Kim Hansen was accepted and presented
at the Symposium on Computational Geometry 2005
Multimedia and Video session in Pisa, Italy, in June 2005.
Some more animations and pictures describing a paper on
drawing planar graphs on curves
is available both in English and Italian!
Software for drawing arrangement graphs in 3 dimensions was
developed by Ray Dufresne:
ArrangePak3D
In the Summer of 2002, I had 2 students working for me on upgrading the
packages described below and making some
lovely animations related to 3d graph drawing.
One project of interest to researchers in visibility graphs is
the VisPak package
of visibility algorithms written here at the U. of Lethbridge
under my supervision.
My students have also written a package for manipulation
of arrangements of lines and pseudo-lines (ArrangePak) and
a package for 3-d orthogonal drawing of graphs (OrthoPak).
This software is freely available for research and teaching purposes.
You may download the
PACKAGES.
An applet displaying the Z-planes of a
3-D orthogonal drawing of K100
is available that displays some joint work with T. Biedl,
T. Shermer, and S. Whitesides.
An applet implementing an algorithm for determining
an inducing path of length n in a set of lines
can be viewed - joint work with J. Bose, and H. Everett.
A brief animation of some work on an orthogonal 3-d
construction technique that we are developing can be viewed:
Compressed version (about 4M)
Uncompressed (13M)
The following is an animated gif of some work on 3d graph drawing.
Can you identify the graph?
Selected Publications and Conference Presentations:
Note that the electronically available papers are for personal use only, and
in some cases copyright rests with a publishing company.
An alternate
research summary
with pictures is also available.
-
Characterizing Bar Line-of-Sight Graphs,
Wismath, S.,
Proceedings of the Symposium on Computational Geometry,
Baltimore, 1985, pp. 147-152.
-
Weighted Visibility Graphs of Bars and Related Flow Problems,
Kirkpatrick, D.; Wismath, S.,
Proceedings of the Workshop on Algorithms and Data Structures, 1989
Ottawa, Lecture Notes in Computer Science 382, Springer-Verlag,
pp. 325-334.
-
Computing the Full Visibility Graph of a Set of Line
Segments,
Wismath,S.,
Information Processing Letters, 42, July 1992, pp. 257-261.
-
Computing the Visibility Polygons of the endpoints of a set
of line Segments
,
Keil, M.; Wismath,S.,
4th Canadian Conference on Computational Geometry, 1992
and technical report UL-CS-92-02.
-
VisPak: A Package of Visibility Algorithms Written in LEDA
Jackson, L.; Pinto, H.; Wismath, S.
,
Technical Report UL-CS-95-1, 1995.
-
Determining bar-representability for ordered weighted graphs,
Kirkpatrick, D.; Wismath, S. ,
Computational Geometry: Theory and Applications,
Vol 6, No. 2, May 1996, pp. 99-122.
See also: Math Reviews Oct. 97.
-
Bounds for Orthogonal 3-D Graph Drawing,
Biedl, T.; Shermer, T.; Whitesides, S.; Wismath, S.;
Journal of Graph Algorithms and Applications
,
(special issue on new trends in Graph Drawing) Vol. 3, No. 4, 1999,
pp. 63-79.
[
(presented at Graph Drawing 97). An earlier abstract appeared in
Lecture Notes in Computer Science 1353, Springer-Verlag, 1997, pp. 76-86.]
-
ArrangePak, OrthoPak and VisPak 2.0
,
Closson, M.; Everett, H; Gartshore, S.; Wismath S;
University of Lethbridge Technical Report TR-CS-01-98, 1998.
-
Visibility Stabs and Depth-First Spiralling on Line Segments
in Output Sensitive Time,
Keil, M.; Mount, D.; Wismath, S.;
Int. J. of Computational Geometry and Applications, Vol 10, No. 5,
Oct. 2000, pp.535-552.
-
Point and Line Segment Reconstruction from Visibility
Information,
Wismath, S.
,
Int. J. of Computational Geometry and Applications, Vol. 10, No. 2 (2000)
pp. 189-200.
[
An early version was presented at the
6th Canadian Conference on Computational Geometry, 1994 pp. 369-374.]
-
Fully Dynamic Three-Dimensional Orthogonal Graph Drawing
Closson, M.; Gartshore, S.; Johansen, J.; Wismath, S.;
Journal of Graph Algorithms and Applications,
Vol 5, No. 2, 2001 pp. 1-34.
See also the
Web page for this paper
[
Accepted and presented at Graph Drawing 99, September 15-19, Prague.
Springer-Verlag Lecture Notes in Computer Science 1731, pp. 49-58, 1999.
Preliminary versions appeared as:
University of Lethbridge Technical Report TR-CS-01-99, May 1999.
]
-
Orthogonal Polygon Reconstruction from Stabbing Information,
Jackson, L.; Wismath, S.,
Computational Geometry: Theory and Applications, Vol. 23, No. 1,
pp. 69-83, July 2002.
[
An early version appeared in:
Proceedings of the 8th Canadian Conference on Computational Geometry,
Ottawa, August 1996, pp. 44-49.
]
-
Straight-Line Drawings on Restricted Integer Grids in Two and Three
Dimensions;
Felsner, S.; Liotta, G.; Wismath, S.;
in (special issue)
Journal of Graph Algorithms and Applications,
Vol. 7, no. 4, pp. 363-398, 2003.
Animations
[
Accepted and presented at
Graph Drawing 2001 in Vienna, Sept.23-26.
Springer-Verlag Lecture Notes in Computer Science 2265, pp. 328-342.
An older much less detailed version appeared as
U. of Lethbridge Technical Report TR-CS-01-01, May 2001.
]
-
Properties of Arrangement Graphs,
Bose, J.; Everett, H.; Wismath, S.;
Int. J. of Computational Geometry and Applications
Vol 13, No. 6, Dec. 2003, pp. 447--462.
[Presented at 14th European Conference on Computational Geometry,
Barcelona, Spain, March 1998.
See also:
University of Lethbridge Technical Report #CS-01-97, Sept. 1997.
A preliminary version of one of these results appeared as:
McGill Technical Report SOCS96-10, Dec. 1996, pp 1-10.
]
-
The k-lines Drawability Problem for Series-Parallel Graphs ;
Di Giacomo, Liotta, Wismath;
U of Lethbridge Technical Report TR-CS-02-02, pp. 1-32
Animation
A preliminary version was
accepted and presented at CCCG02 ,
August 12-14, 2002.
-
3-Dimensional Straight-Line Graph Drawing ,
S. Wismath,
U of Lethbridge Technical Report TR-CS-01-02, pp. 1-11, Dec. 2002
[As presented at the
Journées de Géométrie
Algorithmique 2002
held in Obernai, France,
Oct 14-18, 2002.]
-
GLuskap: Visualization and Manipulation of Graph Drawings in 3D ;
Dyck, B.; Joevenazzo, J.; Nickle, E.; Wilsdon, J.; Wismath, S.
Poster/demo accepted at
Graph Drawing 2003,
September 2003, Perugia, Italy.
-
Drawing Kn in Three Dimensions with Two Bends Per Edge ;
Dyck, B.; Joevenazzo, J.; Nickle, E.; Wilsdon, J.; Wismath, S.;
University of Lethbridge Technical Report #CS-01-04, January 2004, pp. 2-7.
-
ArrangePak-3D User's Manual
;
Dufresne, R.; Wismath, S.;
University of Lethbridge Technical Report #CS-02-04, July 2004, pp. 1-21.
The
ArrangePak3D software is available for download.
- GLuskap 2.4 Manual ;
B. Dyck, S. Hanlon, S. Wismath;
University of Lethbridge Technical Report #CS-03-04, October, 2004, pp. 1--28.
The
GLuskap software is available for download.
-
Arrangement for an Upright Bass; animation by
Kim Hansen, S. Wismath;
Honorable mention at Graph Drawing 2004
freestyle contest, New York, Oct. 2004. Springer-Verlag LNCS 3383, pp. 514--515.
-
Curve-constrained drawings of planar graphs
;
E. Di Giacomo, W. Didimo, G. Liotta, S.K. Wismath;
Computational Geometry: Theory and Applications, Vol 30, No. 1, Jan 2005, pp. 1-23.
Animations and software are available at the
Web site .
[Accepted and presented at:
WG2003
29th Workshop on Graph Theoretic Concepts in Computer Science,
June 2003.
Proceedings published in
Springer-Verlag Lecture Notes in Computer Science 2880,
pp. 192-204, Oct. 2003 ]
-
Animation of Curve-constrained drawings of planar graphs;
K. Hansen, S. Wismath;
Accepted and presented at:
Symposium on Computational Geometry (Video, Multi-Media session)
, Pisa, Italy. Proceedings of the 21st Symp. on Comp. Geom. (ACM), June 2005, pp. 374-375.
-
Maintaining Visibility Information of Planar Point Sets
with a Moving Viewpoint;
O. Devillers, V. Dujmovic, H. Everett, S. Hornus, S. Whitesides, S. Wismath;
Int. J. of Computational Geometry and Applications
Vol 17, Issue 4, August 2007,
pp. 297--304.
[Accepted and presented at:
Proc. 17th Canadian Conference on Computational Geometry, Windsor, pp. 291--294 , Aug. 2005]
-
Drawing K_n in Three Dimensions with One Bend per Edge ;
O. Devillers, H. Everett, S. Lazard, M. Pentcheva, S. Wismath;
Journal of Graph Algorithms and Applications, Vol 10, No. 2, pp. 287-295, 2006.
[
Accepted and presented at: Graph Drawing 2005, Limerick Ireland, Sept. 2005.
Proceedings published in
Springer-Verlag Lecture Notes in Computer Science 3843,
pp. 83--88, 2006.]
- Book Embeddability of Series-Parallel Digraphs ;
Di Giacomo, Didimo, Liotta, Wismath;
Algorithmica, Vol 45, No. 4, Aug. 2006. pp. 531--547.
[Accepted and presented at Graph Drawing 2002, Irvine,
August 26-28, 2002. Springer-Verlag LNCS 2528 pp. 162-173]
- k-colored Point-set Embeddability of Outerplanar Graphs ;
Di Giacomo, Didimo, Liotta, Meijer, Trotta, Wismath;
Journal of Graph Algorithms and Applications, Vol 12, No. 1, pp. 29--49, 2008.
[ Accepted and presented at Graph Drawing 2006, Karlruhe. Proceedings in:
Springer-Verlag Lecture Notes in Computer Science 4372,
pp. 318--329, 2007.]
- Point Set Embeddings of Trees with Edge Constraints;
E. Di Giacomo, W. Didimo, G. Liotta, H. Meijer, S. Wismath;
Computational Geometry: Theory and Applications,
Vol 42, Issues 6-7, August 2009, Pages 664-676.
[Accepted and presented at Graph Drawing 2007, Sydney,
Sept. 23-26, 2007. Proceedings in: Springer-Verlag LNCS 4875 pp. 113--124.]
- Universal Sets of n Points for 1-bend Drawings of Planar Graphs with n Vertices;
H. Everett, S. Lazard, G. Liotta, S. Wismath;
Discrete and Computational Geometry
Vol 43, No. 2, March 2010, pp. 272--288.
DOI: 10.1007/s00454-009-9149-3.
[Accepted and presented at Graph Drawing 2007, Sydney,
Sept. 23-26, 2007. Proceedings in: Springer-Verlag LNCS 4875 pp. 345--351.]
- A note on alpha-drawable k-trees;
S. Stolpner, J. Lenchner, G. Liotta, D. Bremner, C. Paul, M. Pouget and S. Wismath.
Accepted and presented at Cdn Conf on Comp. Geom 08,
Montreal, 2008.
- Constrained Point-Set Embeddability of Planar Graphs;
Di Giacomo, Didimo, Liotta, Meijer, Wismath;
Int. J. of Computational Geometry and Applications Vol. 20, Issue 5, Oct. 2010, pp. 577-600.
[Accepted and presented at Graph Drawing 2008, Crete,
Sept. 2008. Proceedings in: Springer-Verlag LNCS 5417 pp. 360--371.]
-
Volume Requirements of 3D Upward Drawings;
E. Di Giacomo, G. Liotta, H. Meijer, S. Wismath;
Discrete Mathematics 309 (2009), pp. 1824-1837
[
Accepted and presented at: Graph Drawing 2005, Limerick Ireland, Sept. 2005.
Proceedings published in
Springer-Verlag Lecture Notes in Computer Science 3843,
pp. 101-110, 2006.]
- Matched Drawability of Graph Pairs and of Graph Triples;
Luca Grilli, Seok-Hee Hong, Giuseppe Liotta, Henk Meijer and Steve Wismath;
Computational Geometry: Theory and Applications
Volume 43, Issues 6-7, Pages 611-634, August 2010
[
Accepted and presented at: WALCOM2009
India].
- On Line Sets Supporting Planar Graphs;
V. Dujmovic, W. Evans, S. Kobourov, G. Liotta, C. Weibel, S. Wismath;
Accepted and presented at Graph Drawing 2010, Konstanz.
Springer-Verlag Lecture Notes in Computer Science, Vol. 6502,
pp. 177-182, 2011
-
On Point-sets that Support Planar Graphs
;
V. Dujmovic, W. Evans, S. Lazard, W. Lenhart, G. Liotta, D. Rappaport, S. Wismath;
Computational Geometry: Theory and Applications
Vol. 46, Issue 1, pp. 29--50, Jan. 2013.
[
Accepted and presented at: Graph Drawing 2011, Eindhoven.
Springer-Verlag Lecture Notes in Computer Science, Vol. 7034,
pp. 64--74, 2012.
]
- Monotone Drawings of Graphs with Fixed Embedding
P. Angelini, W. Didimo, S. Kobourov, T. Michedlidze, V. Roselli, A. Symvonis, S. Wismath;
Algorithmica
Vol. 71 Issue 2, pp. 233--257, Feb. 2015.
[ Accepted and presented at: Graph Drawing 2011, Eindhoven.
Springer-Verlag Lecture Notes in Computer Science, Vol. 7034,
pp. 379--390, 2012.
]
- Planar and Quasi Planar Simultaneous Geometric Embedding
E. Di Giacomo, W. Didimo, G. Liotta, H. Meijer, S. Wismath;
The Computer Journal 2015
doi: 10.1093/comjnl/bxv048
[ Accepted and presented at: Graph Drawing 2014, Wuerzburg.
Springer-Verlag Lecture Notes in Computer Science, Vol. 8871,
pp. 52--63, 2014.
]
- Bar 1 Visibility Graphs vs. other Nearly Planar Graphs;
W. Evans, M. Kaufmann, W. Lenhart, G. Liotta, T. Mchedlidze, S. Wismath;
Journal of Graph Algorithms and Applications,
vol. 18, no. 5, pp. 72--739 (2014)
- Point-set Embedding in Three Dimensions
H. Meijer, S. Wismath;
Journal of Graph Algorithms and Applications,
Vol. 19, no. 1, pp. 243--257 (2015)
[
Accepted and presented at CCCG2012, P.E.I., August, 2012.]
See the
supporting web site.
- Alternating Paths and Cycles of Minimum Length
W. Evans, G. Liotta, H. Meijer, S. Wismath;
Computational Geometry: Theory and Applications, Vol. 58, pp. 124--135,
Oct. 2016
[
Accepted and presented at Graph Drawing 2015, Los Angeles.
Springer-Verlag Lecture Notes in Computer Science, Vol. 9411, pp. 383--394, 2015.
]
-
On the Planar Split Thickness of Graphs
D. Eppstein, P. Kindermann, S. Kobourov, G. Liotta, A. Lubiw, A. Maignan, D. Mondal, H. Vosoughpour, S. Whitesides, S. Wismath;
Accepted and presented at Latin 2016.
Springer-Verlag LNCS, Vol. 9644, pp. 403--415, 2016.
arXiv
-
Polynomial volume point set embedding of graphs in 3D;
F. Barahimi, S. Wismath;
Proc. 28th Canadian Conference on Computational Geometry, SFU, pp. 80--85, Aug. 2016
-
Visibility Representations of Boxes in 2.5 Dimensions;
A. Arleo, C. Binucci, E. Di Giacomo, W. Evans, L. Grilli, G. Liotta, H. Meijer, F. Montecchiani, S. Whitesides, S. Wismath;
Computational Geometry: Theory and Applications, Vol 72, pp. 19--33, June 2018.
[
Graph Drawing 2016, Athens,
Springer-Verlag Lecture Notes in Computer Science Vol. 9801.
]
-
Ortho-polygon Visibility Representations of Embedded Graphs;
E. Di Giacomo, W. Didimo, W. Evans, G. Liotta, H. Meijer, F. Montecchiani, S. Wismath;
Graph Drawing 2016, Athens,
Springer-Verlag Lecture Notes in Computer Science Vol. 9801.
-
Monotone Simultaneous Paths Embeddings in R^d
D. Bremner, O. Devillers, M. Glisse, S. Lazard, G. Liotta, T. Mchedlidze, S. Whitesides, S. Wismath;
Discrete Mathematics and Theoretical Computer Science
Vol. 20, No. 1, Jan. 2018.
[ accepted and presented at:
Graph Drawing 2016, Athens,
Springer-Verlag Lecture Notes in Computer Science Vol. 9801.
]
-
New results on edge partitions of 1-plane graphs;
E. Di Giacomo, W. Didimo, W. Evans, G. Liotta, H. Meijer, F. Montecchiani, S. Wismath;
Theoretical Computer Science 713, pp. 78--84, 2018.
-
Colored anchored visibility representations in 2D and 3D space;
C. Binucci, E. Di Giacomo, S.H. Hong, G. Liotta, H. Meijer, V. Sacristan, S. Wismath;
Computational Geometry,
Vol. 89,
2020.