Layout of Graphs with Bounded Tree-Width

Details Layout of Graphs with Bounded Tree-Width Layout of Graphs with Bounded Tree-Width

2004-06-16

arxiv.org/abs/cs/0406024v1

SIAM J. Computing 34.3:553-579, 2005

Computer Science

Discrete Mathematics

This is a revised version of a journal paper submitted in October 2002. This paper incorporates the following conference paper

Scientific paper

10.1137/S0097539702416141

A \emph{queue layout} of a graph consists of a total order of the vertices, and a partition of the edges into \emph{queues}, such that no two edges in the same queue are nested. The minimum number of queues in a queue layout of a graph is its \emph{queue-number}. A \emph{three-dimensional (straight-line grid) drawing} of a graph represents the vertices by points in $\mathbb{Z}^3$ and the edges by non-crossing line-segments. This paper contributes three main results: (1) It is proved that the minimum volume of a certain type of three-dimensional drawing of a graph $G$ is closely related to the queue-number of $G$. In particular, if $G$ is an $n$-vertex member of a proper minor-closed family of graphs (such as a planar graph), then $G$ has a $O(1)\times O(1)\times O(n)$ drawing if and only if $G$ has O(1) queue-number. (2) It is proved that queue-number is bounded by tree-width, thus resolving an open problem due to Ganley and Heath (2001), and disproving a conjecture of Pemmaraju (1992). This result provides renewed hope for the positive resolution of a number of open problems in the theory of queue layouts. (3) It is proved that graphs of bounded tree-width have three-dimensional drawings with O(n) volume. This is the most general family of graphs known to admit three-dimensional drawings with O(n) volume. The proofs depend upon our results regarding \emph{track layouts} and \emph{tree-partitions} of graphs, which may be of independent interest.

Affiliated with

Also associated with

No associations

Rating

Layout of Graphs with Bounded Tree-Width does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Layout of Graphs with Bounded Tree-Width, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Layout of Graphs with Bounded Tree-Width will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-219236