## Abstract

A three-dimensional (straight-line grid) drawing of a graph represents the vertices by points in Z and the edges by non-crossing line segments. This research is motivated by the following open problem due to Felsner, Liotta, and Wismath [Graph Drawing '01, Lecture Notes in Comput. Sci., 2002]: does every n-vertex planar graph have a three-dimensional drawing with O(n) volume? We prove that this question is almost equivalent to an existing one-dimensional graph layout problem. A queue layout consists of a linear order ρ of the vertices of a graph, and a partition of the edges into queues, such that no two edges in the same queue are nested with respect to ρ. The minimum number of queues in a queue layout of a graph is its queue-number. Let G be an n-vertex member of a proper minor-closed family of graphs (such as a planar graph). We prove that G has a O(1) × O(1) × O(n) drawing if and only if G has O(1) queue-number. Thus the above question is almost equivalent to an open problem of Heath, Leighton, and Rosenberg [SIAM J. Discrete Math., 1992], who ask whether every planar graph has O(1) queue-number? We also present partial solutions to an open problem of Ganley and Heath [Discrete Appl. Math., 2001], who ask whether graphs of bounded tree-width have bounded queue-number? We prove that graphs with bounded path-width, or both bounded tree-width and bounded maximum degree, have bounded queue-number. As a corollary we obtain three-dimensional drawings with optimal O(n) volume, for series-parallel graphs, and graphs with both bounded tree-width and bounded maximum degree.

Original language | English |
---|---|

Title of host publication | FST TCS 2002 |

Subtitle of host publication | Foundations of Software Technology and Theoretical Computer Science - 22nd Conference, Proceedings |

Publisher | Springer |

Pages | 348-359 |

Number of pages | 12 |

Volume | 2556 LNCS |

ISBN (Print) | 3540002251, 9783540002253 |

DOIs | |

Publication status | Published - 2002 |

Externally published | Yes |

Event | 22nd International Conference on the Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2002 - Kanpur, India Duration: 12 Dec 2002 → 14 Dec 2002 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 2556 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 22nd International Conference on the Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2002 |
---|---|

Country/Territory | India |

City | Kanpur |

Period | 12/12/02 → 14/12/02 |