# School of Mathematics and Statistics - Research Publications

## Search Results

Now showing 1 - 7 of 7
• Item
A Linear-Time Algorithm to Find a Separator in a Graph Excluding a Minor
Reed, B ; Wood, DR (ASSOC COMPUTING MACHINERY, 2009-10-01)
Let G be an n -vertex m -edge graph with weighted vertices. A pair of vertex sets A , B ⊆ V ( G ) is a 2/3 -separation of order | A ∩ B | if A ∪ B = V ( G ), there is no edge between A − B and B − A , and both A − B and B − A have weight at most 2/3 the total weight of G . Let ℓ ∈ Z + be fixed. Alon et al. [1990] presented an algorithm that in O ( n 1/2 m ) time, outputs either a K ℓ -minor of G , or a separation of G of order O ( n 1/2 ). Whether there is a O ( n + m )-time algorithm for this theorem was left as an open problem. In this article, we obtain a O ( n + m )-time algorithm at the expense of a O ( n 2/3 ) separator. Moreover, our algorithm exhibits a trade-off between time complexity and the order of the separator. In particular, for any given ϵ ∈ [0,1/2], our algorithm outputs either a K ℓ -minor of G , or a separation of G with order O ( n (2−ϵ)/3 in O ( n 1 + ϵ + m ) time. As an application we give a fast approximation algorithm for finding an independent set in a graph with no K ℓ-minor.
• Item
Layout of graphs with bounded tree-width
Dujmovic, V ; Morin, P ; Wood, DR (SIAM PUBLICATIONS, 2005-01-01)
• Item
Simultaneous diagonal flips in plane triangulations
Bose, P ; Czyzowicz, J ; Gao, Z ; Morin, P ; Wood, DR (WILEY, 2007-04-01)
• Item
Bounded-degree graphs have arbitrarily large geometric thickness
Barat, J ; Matousek, J ; Wood, D ( 2006)
• Item
Drawings of planar graphs with few slopes and segments
Dujmovic, V ; Eppstein, D ; Suderman, M ; Wood, DR (ELSEVIER SCIENCE BV, 2007-10-01)
• Item
A fixed-parameter approach to 2-layer planarization
Dujmovic, V ; Fellows, M ; Hallett, M ; Kitching, M ; Liotta, G ; McCartin, C ; Nishimura, N ; Ragde, P ; Rosamond, F ; Suderman, M ; Whitesides, S ; Wood, DR (SPRINGER, 2006-06-01)
• Item
On the metric dimension of cartesian products of graphs
Caceres, J ; Hernando, C ; Mora, M ; Pelayo, IM ; Puertas, ML ; Seara, C ; Wood, DR (SIAM PUBLICATIONS, 2007-01-01)