Event calendar file
19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Embeddings of Cubic Halin Graphs: A Surface-by-Surface Inventory
Presented by Prof. Jonathan GROSS
Type: Oral presentation
Track: Keynote lecture
Content
We derive an $O(n^2)$-time algorithm for calculating the sequence of numbers $g_0(G)$, $g_1(G)$, $g_2(G)$, ... of distinct ways to embed a \hbox{3-regular} \textit{Halin graph} $G$ on the respective orientable surfaces $S_0$, $S_1$, $S_2$, ... . Key topological features are a \textit{quadrangular decomposition} of plane Halin graphs and a new \textit{recombinant-strands} reassembly process that fits pieces together three-at-a-vertex. Key algorithmic features are reassembly along a \textit{post-order traversal}, with just-in-time \textit{dynamic assignment of roots} for quadrangular pieces encountered along the tour.
Place
Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled
