Recent Advances in Straight-line Graph Drawing:

Extending Steinitz’s Theorem, Fary’s Theorem and Tutte’s Barycenter Theorem

Extending Steinitz’s Theorem, Fary’s Theorem and Tutte’s Barycenter Theorem

Seok-Hee Hong (홍석희)

School of IT, University of Sydney, Sydney, Australia

School of IT, University of Sydney, Sydney, Australia

2012/01/05 Thu 11AM-12AM

One of the most well-studied criteria in Graph Drawing is straight-line

planar representations of graphs. There are three seminal results on straight-line drawings of planar graphs: the Steinitz’s Theorem, Fary’s theorem, and Tutte’s Barycenter Theorem.

In this talk, I will first review the recent advances in Graph Drawing on extending the Steinitz’s Theorem and Tutte’s Barycenter Theorem to non-convex representations: Star-shaped polyhedra and Star-shaped drawings. Then, I will announce the latest results on extending Fary’s theorem to non-planar graphs, namely 1-planar graphs.

planar representations of graphs. There are three seminal results on straight-line drawings of planar graphs: the Steinitz’s Theorem, Fary’s theorem, and Tutte’s Barycenter Theorem.

In this talk, I will first review the recent advances in Graph Drawing on extending the Steinitz’s Theorem and Tutte’s Barycenter Theorem to non-convex representations: Star-shaped polyhedra and Star-shaped drawings. Then, I will announce the latest results on extending Fary’s theorem to non-planar graphs, namely 1-planar graphs.

Tags: 홍석희