School of Mathematics and Statistics - Research Publications

Permanent URI for this collection

Search Results

Now showing 1 - 10 of 10
  • Item
    Thumbnail Image
    On the Connectivity of Visibility Graphs
    Payne, MS ; Por, A ; Valtr, P ; Wood, DR (SPRINGER, 2012-10-01)
    The visibility graph of a finite set of points in the plane has the points as vertices and an edge between two vertices if the line segment between them contains no other points. This paper establishes bounds on the edge- and vertex-connectivity of visibility graphs. Unless all its vertices are collinear, a visibility graph has diameter at most 2, and so it follows by a result of Plesn\'ik (1975) that its edge-connectivity equals its minimum degree. We strengthen the result of Plesn\'ik by showing that for any two vertices v and w in a graph of diameter 2, if deg(v) <= deg(w) then there exist deg(v) edge-disjoint vw-paths of length at most 4. Furthermore, we find that in visibility graphs every minimum edge cut is the set of edges incident to a vertex of minimum degree. For vertex-connectivity, we prove that every visibility graph with n vertices and at most l collinear vertices has connectivity at least (n-1)/(l-1), which is tight. We also prove the qualitatively stronger result that the vertex-connectivity is at least half the minimum degree. Finally, in the case that l=4 we improve this bound to two thirds of the minimum degree.
  • Item
    Thumbnail Image
    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
    Thumbnail Image
    Layout of graphs with bounded tree-width
    Dujmovic, V ; Morin, P ; Wood, DR (SIAM PUBLICATIONS, 2005-01-01)
  • Item
    Thumbnail Image
    Simultaneous diagonal flips in plane triangulations
    Bose, P ; Czyzowicz, J ; Gao, Z ; Morin, P ; Wood, DR (WILEY, 2007-04-01)
  • Item
    Thumbnail Image
    Irreducible triangulations are small
    Joret, G ; Wood, DR (ACADEMIC PRESS INC ELSEVIER SCIENCE, 2010-09-01)
  • Item
    Thumbnail Image
    Contractibility and the Hadwiger Conjecture
    Wood, DR (ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD, 2010-12-01)
  • Item
    Thumbnail Image
    Bounded-degree graphs have arbitrarily large geometric thickness
    Barat, J ; Matousek, J ; Wood, D ( 2006)
  • Item
    Thumbnail Image
    Drawings of planar graphs with few slopes and segments
    Dujmovic, V ; Eppstein, D ; Suderman, M ; Wood, DR (ELSEVIER SCIENCE BV, 2007-10-01)
  • Item
    Thumbnail Image
    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
    Thumbnail Image
    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)