10 citations · 12 across the 4 of their papers we have counts for
5 papers
Drawing a Graph in a Hypercube
David R. Wood
A -dimensional hypercube drawing of a graph represents the vertices by distinct points in , such that the line-segments representing the edges do not cross. We study…
Bounded-Degree Graphs have Arbitrarily Large Geometric Thickness
Janos Barat, Jiri Matousek, David R. Wood
The geometric thickness of a graph G is the minimum integer k such that there is a straight line drawing of G with its edge set partitioned into k plane subgraphs. Eppstein [Separa…
Induced Subgraphs of Bounded Degree and Bounded Treewidth
Prosenjit Bose, Vida Dujmovic, David R. Wood
We prove that for all and , every graph with treewidth at most has a `large' induced subgraph , where has treewidth at most and every v…
A Simple Proof of the F{á}ry-Wagner Theorem
David R. Wood
We give a simple proof of the following fundamental result independently due to Fary (1948) and Wagner (1936): Every plane graph has a drawing in which every edge is straight.
Vertex Partitions of Chordal Graphs
David R. Wood
A \emph{-tree} is a chordal graph with no -clique. An \emph{-tree-partition} of a graph is a vertex partition of into `bags', such that contracting each bag…