6 papers
On the spanning structure hierarchy of 3-connected planar graphs
On-Hei Solomon Lo
The prism over a graph is the Cartesian product of with the complete graph . is prism-hamiltonian if the prism over has a Hamilton cycle. A good even cactus is…
Hamiltonian cycles in 4-connected planar and projective planar triangulations with few 4-separators
On-Hei Solomon Lo, Jianguo Qian
Whitney proved in 1931 that every 4-connected planar triangulation is hamiltonian. Later in 1979, Hakimi, Schmeichel and Thomassen conjectured that every such triangulation on …
Tight gaps in the cycle spectrum of 3-connected planar graphs
Qing Cui, On-Hei Solomon Lo
For any positive integer , define (respectively, ) to be the minimal integer such that every 3-connected planar graph (respectively, 3-connected cubic…
Find Subtrees of Specified Weight and Cycles of Specified Length in Linear Time
On-Hei Solomon Lo
We apply the Euler tour technique to find subtrees of specified weight as follows. Let such that , and $2k - 4g - h +…
Compact Cactus Representations of all Non-Trivial Min-Cuts
On-Hei Solomon Lo, Jens M. Schmidt, Mikkel Thorup
Recently, Kawarabayashi and Thorup presented the first deterministic edge-connectivity recognition algorithm in near-linear time. A crucial step in their algorithm uses the existen…
Cut Tree Structures with Applications on Contraction-Based Sparsification
On-Hei Solomon Lo, Jens M. Schmidt
We introduce three new cut tree structures of graphs in which the vertex set of the tree is a partition of and contractions of tree vertices satisfy sparsification requi…