Queue Layouts of Graphs with Bounded Degree and Bounded Genus

Abstract: Motivated by the question of whether planar graphs have bounded queue-number, we prove that planar graphs with maximum degree

D e l t a

have queue-number

O (D e l t a^{2})

, which improves upon the best previous bound of

O (D e l t a^{6})

. More generally, we prove that graphs with bounded degree and bounded Euler genus have bounded queue-number. In particular graphs with Euler genus

g

and maximum degree

D e l t a

have queue-number

O (g + D e l t a^{2})

. As a byproduct we prove that if planar graphs have bounded queue-number, then graphs of Euler genus

g

have queue-number

O (g)

.

This page was built for publication: Queue Layouts of Graphs with Bounded Degree and Bounded Genus